計數(shù)排序（Counting Sort）

• 計數(shù)排序是一個非基于比較的排序算法特咆，該算法于1954年由 Harold H. Seward 提出妒牙。它的優(yōu)勢在于在對一定范圍內(nèi)的整數(shù)排序時贵扰，快于任何比較排序算法。
• 排序思路:
  • 1.找出待排序數(shù)組最大值
  • 2.定義一個索引最大值為待排序數(shù)組最大值的數(shù)組
  • 3.遍歷待排序數(shù)組, 將待排序數(shù)組遍歷到的值作新數(shù)組索引

  • 4.在新數(shù)組對應(yīng)索引存儲值原有基礎(chǔ)上+1

    
    

• 簡單代碼實(shí)現(xiàn):

int main()
{
    // 待排序數(shù)組
    int nums[5] = {3, 1, 2, 0, 3};
    // 用于排序數(shù)組
    int newNums[4] = {0};
    // 計算待排序數(shù)組長度
    int len = sizeof(nums) / sizeof(nums[0]);
    // 遍歷待排序數(shù)組
    for(int i = 0; i < len; i++){
        // 取出待排序數(shù)組當(dāng)前值
        int index = nums[i];
        // 將待排序數(shù)組當(dāng)前值作為排序數(shù)組索引
        // 將用于排序數(shù)組對應(yīng)索引原有值+1
        newNums[index] = newNums[index] +1;
    }
    
    // 計算待排序數(shù)組長度
    int len2 = sizeof(newNums) / sizeof(newNums[0]);
    // 輸出排序數(shù)組索引, 就是排序之后結(jié)果
    for(int i = 0; i < len2; i++){
        for(int j = 0; j < newNums[i]; j++){
            printf("%i\n", i);
        }
    }
    /*
    // 計算待排序數(shù)組長度
    int len2 = sizeof(newNums) / sizeof(newNums[0]);
    // 還原排序結(jié)果到待排序數(shù)組
    for(int i = 0; i < len2; i++){
        int index = 0;
        for(int i = 0; i < len; i++){
            for(int j = 0; j < newNums[i]; j++){
                nums[index++] = i;
            }
        }
    }
    */
    return 0;
}

選擇排序

• 選擇排序(Selection sort)是一種簡單直觀的排序算法浇雹。它的工作原理如下稿蹲。首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再從剩余未排序元素中繼續(xù)尋找最小元素,然后放到排序序列末尾。以此類推,直到所有元素均排序完畢皂冰。

  
  

• 排序思路:

  • 假設(shè)按照升序排序
  • 1.用第0個元素和后面所有元素依次比較
  • 2.判斷第0個元素是否大于當(dāng)前被比較元素, 一旦小于就交換位置
  • 3.第0個元素和后續(xù)所有元素比較完成后, 第0個元素就是最小值
  • 4.排除第0個元素, 用第1個元素重復(fù)1~3操作, 比較完成后第1個元素就是倒數(shù)第二小的值
  • 以此類推, 直到當(dāng)前元素沒有可比較的元素, 排序完成

• 代碼實(shí)現(xiàn):

// 選擇排序
void selectSort(int numbers[], int length) {
    
    // 外循環(huán)為什么要-1?
    // 最后一位不用比較, 也沒有下一位和它比較, 否則會出現(xiàn)錯誤訪問
    for (int i = 0; i < length; i++) {
        for (int j = i; j < length - 1; j++) {
            // 1.用當(dāng)前元素和后續(xù)所有元素比較
            if (numbers[i] < numbers[j + 1]) {
                //  2.一旦發(fā)現(xiàn)小于就交換位置
                swapEle(numbers, i, j + 1);
            }
        }
    }
}
// 交換兩個元素的值, i/j需要交換的索引
void swapEle(int array[], int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

冒泡排序

• 冒泡排序(Bubble Sort)是一種簡單的排序算法店展。它重復(fù) 地走訪過要排序的數(shù)列,一次比較兩個元素,如果他們的順序錯誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換,也就是說該數(shù)列已經(jīng)排序完成秃流。這個算法的名字由來是因?yàn)樵叫〉脑貢?jīng)由交換慢慢“浮”到數(shù)列的頂端赂蕴。

  
  
• 排序思路:
  • 假設(shè)按照升序排序
  • 1.從第0個元素開始, 每次都用相鄰兩個元素進(jìn)行比較
  • 2.一旦發(fā)現(xiàn)后面一個元素小于前面一個元素就交換位置
  • 3.經(jīng)過一輪比較之后最后一個元素就是最大值
  • 4.排除最后一個元素, 以此類推, 每次比較完成之后最大值都會出現(xiàn)再被比較所有元素的最后
  • 直到當(dāng)前元素沒有可比較的元素, 排序完成
• 代碼實(shí)現(xiàn):

// 冒泡排序
void bubbleSort(int numbers[], int length) {
    for (int i = 0; i < length; i++) {
        // -1防止`角標(biāo)越界`: 訪問到了不屬于自己的索引
        for (int j = 0; j < length - i - 1; j++) {
           //  1.用當(dāng)前元素和相鄰元素比較
            if (numbers[j] < numbers[j + 1]) {
                //  2.一旦發(fā)現(xiàn)小于就交換位置
                swapEle(numbers, j, j + 1);
            }
        }
    }
}
// 交換兩個元素的值, i/j需要交換的索引
void swapEle(int array[], int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

插入排序

• 插入排序（Insertion-Sort）的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列剔应，對于未排序數(shù)據(jù)睡腿，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入峻贮。

  
  
• 排序思路:
  • 假設(shè)按照升序排序
  • 1.從索引為1的元素開始向前比較, 一旦前面一個元素大于自己就讓前面的元素先后移動
  • 2.直到?jīng)]有可比較元素或者前面的元素小于自己的時候, 就將自己插入到當(dāng)前空出來的位置
• 代碼實(shí)現(xiàn):

int main()
{
    // 待排序數(shù)組
    int nums[5] = {3, 1, 2, 0, 3};
    // 0.計算待排序數(shù)組長度
    int len = sizeof(nums) / sizeof(nums[0]);

    //  1.從第一個元素開始依次取出所有用于比較元素
    for (int i = 1; i < len; i++)
    {
        // 2.取出用于比較元素
        int temp = nums[i];
        int j = i;
        while(j > 0){
            // 3.判斷元素是否小于前一個元素
            if(temp < nums[j - 1]){
                // 4.讓前一個元素向后移動一位
                nums[j] = nums[j - 1];
            }else{
                break;
            }
            j--;
        }
        // 5.將元素插入到空出來的位置
        nums[j] = temp;
    }
}

int main()
{
    // 待排序數(shù)組
    int nums[5] = {3, 1, 2, 0, 3};
    // 0.計算待排序數(shù)組長度
    int len = sizeof(nums) / sizeof(nums[0]);

    //  1.從第一個元素開始依次取出所有用于比較元素
    for (int i = 1; i < len; i++)
    {
        // 2.遍歷取出前面元素進(jìn)行比較
        for(int j = i; j > 0; j--)
        {
            // 3.如果前面一個元素大于當(dāng)前元素,就交換位置
            if(nums[j-1] > nums[j]){
                int temp = nums[j];
                nums[j] = nums[j - 1];
                nums[j - 1] = temp;
            }else{
                break;
            }
        }
    }
}

希爾排序

• 1959年Shell發(fā)明席怪，第一個突破O(n2)的排序算法，是簡單插入排序的改進(jìn)版纤控。它與插入排序的不同之處在于挂捻，它會優(yōu)先比較距離較遠(yuǎn)的元素。希爾排序又叫縮小增量排序船万。

  
  
• 排序思路:
  • 1.希爾排序可以理解為插入排序的升級版, 先將待排序數(shù)組按照指定步長劃分為幾個小數(shù)組
  • 2.利用插入排序?qū)π?shù)組進(jìn)行排序, 然后將幾個排序的小數(shù)組重新合并為原始數(shù)組
  • 3.重復(fù)上述操作, 直到步長為1時,再利用插入排序排序即可
• 代碼實(shí)現(xiàn):

int main()
{
    // 待排序數(shù)組
    int nums[5] = {3, 1, 2, 0, 3};
    // 0.計算待排序數(shù)組長度
    int len = sizeof(nums) / sizeof(nums[0]);

// 2.計算步長
    int gap = len / 2;
    do{
        //  1.從第一個元素開始依次取出所有用于比較元素
        for (int i = gap; i < len; i++)
        {
            // 2.遍歷取出前面元素進(jìn)行比較
            int j = i;
            while((j - gap) >= 0)
            {
                printf("%i > %i\n", nums[j - gap], nums[j]);
                // 3.如果前面一個元素大于當(dāng)前元素,就交換位置
                if(nums[j - gap] > nums[j]){
                    int temp = nums[j];
                    nums[j] = nums[j - gap];
                    nums[j - gap] = temp;
                }else{
                    break;
                }
                j--;
            }
        }
        // 每個小數(shù)組排序完成, 重新計算步長
        gap = gap / 2;
    }while(gap >= 1);
}

江哥提示:
對于初學(xué)者而言, 排序算法一次不易于學(xué)習(xí)太多, 咋們先來5個玩一玩, 后續(xù)繼續(xù)講解其它5個

折半查找

• 基本思路
• 在有序表中,取中間元素作為比較對象,若給定值與中間元素的要查找的數(shù)相等,則查找成功;若給定值小于中間元素的要查找的數(shù),則在中間元素的左半?yún)^(qū)繼續(xù)查找;
• 若給定值大于中間元素的要查找的數(shù),則在中間元素的右半?yún)^(qū)繼續(xù)查找刻撒。不斷重復(fù)上述查找過 程,直到查找成功,或所查找的區(qū)域無數(shù)據(jù)元素,查找失敗

• 實(shí)現(xiàn)步驟

• 在有序表中,取中間元素作為比較對象,若給定值與中間元素的要查找的數(shù)相等,則查找成功;

• 若給定值小于中間元素的要查找的數(shù),則在中間元素的左半?yún)^(qū)繼續(xù)查找;

• 若給定值大于中間元素的要查找的數(shù),則在中間元素的右半?yún)^(qū)繼續(xù)查找。

• 不斷重復(fù)上述查找過 程,直到查找成功,或所查找的區(qū)域無數(shù)據(jù)元素,查找失敗耿导。

  
  

• 代碼實(shí)現(xiàn)

int findKey(int values[], int length, int key) {
    // 定義一個變量記錄最小索引
    int min = 0;
    // 定義一個變量記錄最大索引
    int max = length - 1;
    // 定義一個變量記錄中間索引
    int mid = (min + max) * 0.5;
    
    while (min <= max) {
        // 如果mid對應(yīng)的值 大于 key, 那么max要變小
        if (values[mid] > key) {
            max = mid - 1;
            // 如果mid對應(yīng)的值 小于 key, 那么min要變
        }else if (values[mid] < key) {
            min = mid + 1;
        }else {
            return mid;
        }
        // 修改完min/max之后, 重新計算mid的值
        mid = (min + max) * 0.5;
    }
    return -1;
}

進(jìn)制轉(zhuǎn)換(查表法)

• 實(shí)現(xiàn)思路:
  • 將二進(jìn)制声怔、八進(jìn)制、十進(jìn)制舱呻、十六進(jìn)制所有可能的字符都存入數(shù)組
  • 利用按位與運(yùn)算符和右移依次取出當(dāng)前進(jìn)制對應(yīng)位置的值
  • 利用取出的值到數(shù)組中查詢當(dāng)前位輸出的結(jié)果
  • 將查詢的結(jié)果存入一個新的數(shù)組, 當(dāng)所有位都查詢存儲完畢, 新數(shù)組中的值就是對應(yīng)進(jìn)制的值
• 代碼實(shí)現(xiàn)

#include <stdio.h>
void toBinary(int num)
{
    total(num, 1, 1);
}
void toOct(int num)
{
    total(num, 7, 3);
}
void toHex(int num)
{
    total(num, 15, 4);
}

void total(int num , int base, int offset)
{
    //    1.定義表用于查詢結(jié)果
    char cs[] = {
        '0', '1', '2', '3', '4', '5',
        '6', '7', '8', '9', 'a', 'b',
        'c', 'd', 'e', 'f'
    };
    //    2.定義保存結(jié)果的數(shù)組
    char rs[32];
    //    計算最大的角標(biāo)位置
    int length = sizeof(rs)/sizeof(char);
    int pos = length;//8

    while (num != 0) {
        int index = num & base;
        rs[--pos] = cs[index];
        num = num >> offset;
    }

    for (int i = pos; i < length; i++) {
        printf("%c", rs[i]);
    }
    printf("\n");
}
int main()
{
    toBinary(9);
    return 0;
}