日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

C語言完整實現12種排序算法(小結)_C 語言

作者：歐拉恒等式 ? 更新時間： 2022-07-08 編程語言

1.冒泡排序

思路：比較相鄰的兩個數字，如果前一個數字大，那么就交換兩個數字，直到有序。
時間復雜度O(n^2)，穩定性：這是一種穩定的算法。
代碼實現：

void bubble_sort(int arr[],size_t len){
    size_t i,j;
    for(i=0;i<len;i++){    
        bool hasSwap = false;        //優化，判斷數組是否已經有序，如果有序可以提前退出循環
        for(j=1;j<len-i;j++){        //這里j<len-i是因為最后面的肯定都是最大的，不需要多進行比較
            if(arr[j-1]>arr[j]){    //如果前一個比后一個大
                swap(&arr[j-1],&arr[j]);    //交換兩個數據
                hasSwap = true;
            }    
        }
        if(!hasSwap){
            break;    
        }
    }
}

2.插入排序

思路：把一個數字插入一個有序的序列中，使之仍然保持有序，如對于需要我們進行排序的數組，我們可以使它的前i個數字有序，然后再插入i+1個數字，插入到合適的位置使之仍然保持有序，直到所有的數字有序。
時間復雜度：O(n^2) 穩定性：穩定的算法
代碼實現：

void insert_sort(int arr[],int len){
    int i,j;
    for(i=1;i<len;i++){
        int key = arr[i];            //記錄當前需要插入的數據
        for(j= i-1;i>=0&&arr[j]>key;j--){    //找到插入的位置
            arr[j+1] = arr[j];                //把需要插入的元素后面的元素往后移
        }
        arr[j+1] = key;        //插入該元素
    }
}

3.折半插入排序

思路：本質上是插入排序，但是通過半分查找法找到插入的位置，讓效率稍微快一點。
時間復雜度：O(n^2)，穩定性：穩定的算法。
代碼實現：

void half_insert_sort(int arr[],int len){
    int i,j;
    for(i=1;i<len;i++){
        int key = arr[i];
        int left = 0;
        int right = i-1;
        while(left<=right){    //半分查找找到插入的位置
            int mid = (left+right)/2;
            if(key<arr[mid]){
                right = mid-1;    
            }else{
                left = mid+1;    
            }    
        }
        for(j=i-1;j>=left;j--){        //把后面的元素往后移
            arr[j+1]=arr[j];    
        }
        arr[j+1] = key;    //插入元素
    }
}

4.希爾排序

思路：先取一個正整數d1<n，把所有序號相隔d1的數組元素放一組，組內進行直接插入排序；然后取d2<d1，重復上述分組和排序操作；直至di=1，即所有記錄放進一個組中排序為止。
時間復雜度：O(n^1.3) ,算法效率上大大提高 。穩定性：不穩定的算法。
代碼實現：

void shell_sort(int arr[],int len){    //本質上也是一種插入排序，避免了大量數據的移動，在每一組排序過后，每個數據已經到了大致的位置。
    int i,j;
    int step=0;
    for(step = len/2;step>=1;step=step/2){    //分組  分為step組,對每組的元素進行插入排序
        for(i=step;i<len;i++){
            int key = arr[i];
            for(j=i-step;j>=0&&arr[j]>key;j=j-step){
                arr[j+step] = arr[j];    
            }    
            arr[j+step] = key;
        }
    }
}

5.選擇排序

思路：通過循環找到最大值所在的位置，然后把最大值和最后一個元素進行交換，通過循環直到所有的數據有序。
時間復雜度：O(n^2) 穩定性：不穩定的算法
代碼實現：

void select_sort(int arr[],size_t len){
    size_t i,j;
    for(i=0;i<len-1;i++){
        int max = 0;        //最大值下標
        for(j=1;j<len-i;j++){
            if(arr[max]<arr[j]){    //找到最大值的下標
                max = j;    
            }    
        }
        if(max!=j-1){    
            swap(&arr[max],&arr[j-1]);    //把最后一個元素和最大值進行交換
        }
    }
}

6.雞尾酒排序

思路：選擇排序的一種改進，一次循環直接找到最大值和最小值的位置，把最大值和最后一個元素進行交換，最小值和最前一個元素進行交換，所以最外層的循環只需要執行len/2次即可
時間復雜度：O(n^2) 穩定性：不穩定的算法
代碼實現：

void cocktail_sort(int arr[],size_t len){
    size_t i,j;
    for(i=0;i<len/2;i++){
        int max = i;    //最大值下標
        int min = i;    //最小值下標
        for(j=i+1;j<len-i;j++){
            if(arr[max]<arr[j]){    //找到最大值下標
                max = j;    
            }    
            if(arr[min]>arr[j]){    //找到最小值下標
                min = j;    
            }
        }
        if(max!=j-1){
            swap(&arr[max],&arr[j-1]);        //交換最大值和未進行排序的最后一個元素
        }
        if(min == j-1){    //如果最小值在未進行排序的最后一個位置，那么經過最大值的交換，已經交換到了最大值所在的位置
            min = max;        //把最小值的坐標進行改變
        }
        if(min!=i){
            swap(&arr[i],&arr[min]);    //交換最小值和未進行排序的最前的元素
        }
    }
}

7.堆排序

思路：把數據進行大堆化，然后依次交換堆頂(最大值)和最后一個元素,在使堆頂重新大堆化，最后循環過后數組便有序。
過程：
最大堆調整（Max Heapify）：將堆的末端子節點作調整，使得子節點永遠小于父節點
創建最大堆（Build Max Heap）：將堆中的所有數據重新排序
堆排序（HeapSort）：移除位在第一個數據的根節點，并做最大堆調整的遞歸運算
時間復雜度：O(nlgn) 穩定性：不穩定的算法
實現代碼：

void re_heap(int arr[],size_t index,size_t len){
    size_t child = 2*index+1;    //左節點坐標
    int key = arr[index];    //當前節點值
    while(child<len){
        if(child+1<len&&arr[child]<arr[child+1]){    //如果右節點存在且右節點的值比左節點大，那就child記錄較大字節點的坐標
            child++;    
        }    
        if(arr[child]>key){    //如果子節點的值比根節點的值大
            arr[index] = arr[child];    //改變根節點的值
        }else{
            break;    
        }
        index = child;
        child = 2*index+1;
    }
    arr[index] = key;        //插入記錄好的值
}
void heap_sort(int arr[],size_t len){
    int i;
    for(i=len/2;i>=0;i--){
        re_heap(arr,i,len);        //對第i個根節點進行大堆化
    }
    for(i=len-1;i>0;i--){
        swap(&arr[0],&arr[i]);    //交換第一個和最后一個元素
        re_heap(arr,0,i);    //對第一個元素進行大堆化
    }
}

8.快速排序

思路：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
過程：
(1)首先設定一個分界值，通過該分界值將數組分成左右兩部分
(2)將大于或等于分界值的數據集中到數組右邊，小于分界值的數據集中到數組的左邊。此時，左邊部分中各元素都小于或等于分界值，而右邊部分中各元素都大于或等于分界值。
(3)然后，左邊和右邊的數據可以獨立排序。對于左側的數組數據，又可以取一個分界值，將該部分數據分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側的數組數據也可以做類似處理。
(4)重復上述過程，可以看出，這是一個遞歸定義。通過遞歸將左側部分排好序后，再遞歸排好右側部分的順序。當左、右兩個部分各數據排序完成后，整個數組的排序也就完成了。
時間復雜度：O(nlog2n) 穩定性：不穩定的算法
代碼實現：

void quick_sort(int arr[],size_t left,size_t right){
    if(left>=right){    //如果只有一個元素，那就是有序的，返回
        return;    
    }
    int i = left;
    int j = right;
    int key = arr[left];    //基準值
    while(i<j){    //找到基準值的位置，使得基準值右邊的元素都比基準值大，左邊的元素都比基準值小
        while(i<j&&arr[j]>=key){    //從右邊找一個比基準值小的數，
            --j;
        }
        arr[i] = arr[j];//把這個值放到基準值的位置處
        while(i<j&&arr[i]<=key){    //從左邊找一個比基準值大的數
            ++i;    
        }
        arr[j] = arr[i];        //把這個元素放到j的位置
    }
    arr[i] = key;
    if(i-left>1)    //元素個數至少兩個才進行遞歸調用，這樣可以少一次遞歸
        quick_sort(arr,left,i-1);    //對基準值左邊的元素進行排序
    if(right-i>1)
        quick_sort(arr,i+1,right);    //對基準值右邊的元素進行排序
}

9.歸并排序

思路：對于兩個有序的子序列，可以把它們合并在一起，變成一個新的完全有序的序列，因此歸并排序和快排差不多，都是遞歸的進行。
時間復雜度：O(nlog2n) 穩定性：穩定的算法
代碼實現：

void merge(int arr[],int left,int right){
    int i,j,k;
    int mid = (left+right)/2;
    int len = mid-left+1;
    int *temp = malloc(sizeof(arr[0])*len);
    for(i=0;i<len;i++){
        temp[i] = arr[i+left];    //把這個數組的所有元素都復制到臨時數組中
    }
    i=0,j=mid+1,k=left;
    while(i<len&&j<=right){
        if(temp[i]<arr[j]){    //把臨時數組的元素和 [mid+1,right]這部分的元素一個一個的進行比較，如果誰小，那么arr里就存放誰的元素
            arr[k++] = temp[i++];    
        }else{
            arr[k++] = arr[j++];    
        }
    }
    while(i<len){    //如果temp這個數組的元素還沒有全部遍歷完，那就把temp后面的元素都復制到arr里面去，
    //因為arr[mid+1,right] 這部分的元素本來就是arr后面部分的有序的元素，所以如果arr[mid+1,right]這部分沒有遍歷完也沒關系的，
        arr[k++] = temp[i++];    
    }
    free(temp);
}
void merge_sort(int arr[],int left,int right){
    if(left>=right){    //如果只有一個元素說明這個序列有序，那就返回
        return;    
    }    
    int mid = (left+right)/2;    //對兩個有序的數組進行排序，
    merge_sort(arr,left,mid);    //對[left,mid]這個區間的元素進行排序
    merge_sort(arr,mid+1,right);    //對[mid+1,right]這個區間內的元素進行排序
    merge(arr,left,right);  //這個序列的[left,mid]為有序的序列 [mid+1,right]也為有序的序列
}

10.計數排序

思路：這是一種基于比較的算法，我們用一個大數組來存放這些數據，這些數據在這個大數組中的表現形式是以這個大數組的下標存在的，比如57,60,42這三個數字進行排序，那么用一個大數組，這個大數組的arr[57] = 1,arr[60] = 1,arr[42] = 1，然后遍歷這個大數組就行了。
時間復雜度：O(n+k),其中這個k為數據的范圍，所以計數排序最適合數據比較集中的數組排序。
穩定性：穩定的算法
代碼實現：

void count_sort(int arr[],size_t len){
    int max = arr[0];    //最大值
    int min = arr[0];    //最小值
    size_t i;
    for(i=0;i<len;i++){
        if(max<arr[i]){    //找到最大值
            max =arr[i];    
        }
        if(min > arr[i]){    //找到最小值
            min = arr[i];    
        }
    }
    int cnt = max-min+1;        //范圍
    int *prr = malloc(cnt*sizeof(int));    //申請臨時空間
    for(i=0;i<cnt;i++){    //這個臨時數組全部置0
        prr[i] = 0;    
    }
    for(i=0;i<len;i++){    //對需要進行排序的序列進行遍歷
        prr[arr[i]-min]++;        //讓下標為(arr[i]-min)的臨時大數組的值+1
    }
    size_t j=0;
    for(i=0;i<cnt;i++){    //遍歷這個臨時數組
        while(prr[i]){    //如果這個數組下標為i的值不等于0
            arr[j++] = i+min;    //那就讓需要進行排序的數組的值為i+min;
            --prr[i];
        }    
    }
    free(prr);        //釋放掉申請的動態內存
}

11.桶排序

思路：工作的原理是將數組分到有限數量的桶子里。每個桶子再個別排序（有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行排序）。桶排序是鴿巢排序的一種歸納結果。
這是一種以消耗大量空間來換取高效率的排序方式，
時間復雜度：O(N+C)，其中C=N*(logN-logM)，M為桶的數量。所以對于桶排序，桶的數量越多，其排序效率越高。
穩定性：穩定的算法
代碼實現：
首先定義桶這個類型：

typedef struct Bucket{
?? ?int vect[100];?? ?//其實這里使用鏈表更好，但是我比較懶，就懶得用鏈表了
?? ?int cnt;?? ?//當前桶內存放數據的個數
}Bucket;


void bucket_sort(int arr[],size_t len){
?? ?int min = arr[0];
?? ?int max = arr[0];
?? ?size_t i;
?? ?for(i=0;i<len;i++){
?? ??? ?if(min>arr[i]){?? ?//找到最小值
?? ??? ??? ?min = arr[i];?? ?
?? ??? ?}
?? ??? ?if(max<arr[i]){?? ?//找到最大值
?? ??? ??? ?max = arr[i];?? ?
?? ??? ?}
?? ?}
?? ?int size = max-min+1;
?? ?Bucket bucket[5] = {};?? ?//其實桶可以動態規劃，但為了方便我這里直接分為5個桶
?? ?for(i=0;i<len;i++){?? ?//遍歷待排序的數組，把每個元素放到相應的桶當中，
?? ?//比如[0,200]之間的元素放到下標為0的桶中，[201,400]之間的元素放到下標為1的桶中..
?? ?//以此類推，直到放完所有的數據
?? ??? ?int index = (arr[i]-min)/(size/5);?? ?//用來判斷當前元素arr[i]需要放到哪個桶當中
?? ??? ?bucket[index].vect[bucket[index].cnt++] = arr[i];
?? ?}
?? ?size_t j=0,k=0;
?? ?for(i=0;i<5;i++){?? ?//對這五個桶進行遍歷
?? ??? ?count_sort(bucket[i].vect,bucket[i].cnt);?? ?//首先對這個桶內的元素進行排序，
?? ??? ?//這里可以調用其他排序方法，也可以遞歸調用當前排序方法，但是為了節省內存，我選擇調用其他排序方法，
?? ??? ?for(j=0;j<bucket[i].cnt;j++){
?? ??? ??? ?arr[k++] = bucket[i].vect[j];?? ?//對排序好的桶進行遍歷，并且把里面的元素復制到arr中去?? ?
?? ??? ?}
?? ?}
}

12.基數排序

基數排序（radix sort）屬于“分配式排序”（distribution sort），又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達到排序的作用，基數排序法是屬于穩定性的排序，其時間復雜度為O (nlog?m)，其中r為所采取的基數，而m為堆數，在某些時候，基數排序法的效率高于其它的穩定性排序法。
解法：
1.首先根據個位數的數值，在走訪數值時將它們分配至編號0到9的桶子中；
2.接下來將這些桶子中的數值重新串接起來，接著再進行一次分配，這次是根據十位數來分配；
3.接下來將這些桶子中的數值重新串接起來，持續進行以上的動作直至最高位數為止。
時間復雜度：設待排序列為n個記錄，d個關鍵碼，關鍵碼的取值范圍為radix，則進行鏈式基數排序的時間復雜度為O(d(n+radix))，其中，一趟分配時間復雜度為O(n)，一趟收集時間復雜度為O(radix)，共進行d趟分配和收集。
穩定性：穩定的算法；
代碼實現：
還是定義桶的類型：

typedef struct Bucket{
?? ?int vect[100];?? ?//同樣的可以用鏈表
?? ?int cnt;
}Bucket;


void base_sort(int arr[],size_t len){
?? ?size_t i;
?? ?Bucket bucket[10] = {};?? ?//十個桶
?? ?int max = arr[0];
?? ?for(i=0;i<len;i++){?? ?//尋找最大值，就可以判斷最大值的位數
?? ??? ?if(arr[i]>max){
?? ??? ??? ?max = arr[i];?? ?
?? ??? ?}?? ?
?? ?}
?? ?size_t j,k;
?? ?int num = 1;?? ?//用來獲得相應位數上的數字的關鍵參數，
?? ?//比如要獲得個位上的參數時num = 1;
?? ?//獲得十位上的數字時num = 10;
?? ?//以此類推
?? ?do{
?? ??? ?for(i=0;i<len;i++){?? ?//遍歷待排序的數組，把每個元素放入相應的桶中
?? ??? ?//比如251，當獲得個位上的數字時，251放到下標為1的桶當中
?? ??? ?//當獲得十位上的數字時,251放到下標為5的桶當中
?? ??? ?//當獲得百位上的數字時,251放到下標為2的桶當中
?? ??? ?//當獲得千位上的數字時,251放到下標為0的桶當中
?? ??? ?//以此類推
?? ??? ??? ?int index = arr[i]/num%10;?? ?//獲得相應位數上的數字
?? ??? ??? ?bucket[index].vect[bucket[index].cnt++] = arr[i];?? ?//把這個數字放到相應的桶中
?? ??? ?}
?? ??? ?k=0;
?? ??? ?for(i=0;i<10;i++){
?? ??? ??? ?for(j=0;j<bucket[i].cnt;j++){
?? ??? ??? ??? ?arr[k++] = bucket[i].vect[j];?? ?//把這些桶按順序依次遍歷，
?? ??? ??? ??? ?//把桶中的元素重新放回arr當中
?? ??? ??? ?}?? ?
?? ??? ??? ?bucket[i].cnt = 0;?? ?//記得讓桶中的cnt變為0,方便下一次存放
?? ??? ?}
?? ??? ?num*=10;?? ?//num*10
?? ?}while(max/=10);//循環條件
}

原文鏈接：https://blog.csdn.net/weixin_42617375/article/details/103536193

欄目分類
最近更新