題目詳情：

給定N個（長整型范圍內的）整數(shù)，要求輸出從小到大排序后的結果。

本題旨在測試各種不同的排序算法在各種數(shù)據(jù)情況下的表現(xiàn)。各組測試數(shù)據(jù)特點如下：

• 數(shù)據(jù)1：只有1個元素；
• 數(shù)據(jù)2：11個不相同的整數(shù)，測試基本正確性；
• 數(shù)據(jù)3：103個隨機整數(shù)；
• 數(shù)據(jù)4：104個隨機整數(shù)；
• 數(shù)據(jù)5：105個隨機整數(shù)；
• 數(shù)據(jù)6：105個順序整數(shù)；
• 數(shù)據(jù)7：105個逆序整數(shù)；
• 數(shù)據(jù)8：105個基本有序的整數(shù)；
• 數(shù)據(jù)9：105個隨機正整數(shù)，每個數(shù)字不超過1000。

  輸入格式:

  輸入第一行給出正整數(shù)N（≤105），隨后一行給出N個（長整型范圍內的）整數(shù)，其間以空格分隔。

  輸出格式:

  在一行中輸出從小到大排序后的結果，數(shù)字間以1個空格分隔，行末不得有多余空格。

  輸入樣例:

  11
  4 981 10 -17 0 -20 29 50 8 43 -5
  

  輸出樣例:

  -20 -17 -5 0 4 8 10 29 43 50 981

主要思路：

把所有提到的排序都嘗試復現(xiàn)一遍（才發(fā)現(xiàn)自己啥也不會）

（一）選擇排序：

（1）簡單選擇排序：

在未排序序列中選出最小元素和序列首位元素交換，剩下來的序列以此類推

#include <stdio.h>
#include <stdlib.h>
#define MAX_NUM 100005
int Data[MAX_NUM];
void Swap(int* data1, int* data2) {
    int temp = *data1;
    *data1 = *data2;
    *data2 = temp;
    return;
}
void SimpleSelectionSort(int num, int data[]) {
    int minIndex;
    for(int i = 0; i < num - 1; i++) {
        minIndex = i;
        for(int j = i + 1; j < num; j++) {
           if(data[j] < data[minIndex]) {
               minIndex = j;
           } 
        }
        Swap(&data[i], &data[minIndex]);
    }
    return;
}
int main() {
    int num;
    scanf("%d", &num);
    for(int i = 0; i < num; i++) {
        scanf("%d", &Data[i]);
    }
    SimpleSelectionSort(num, Data);
    for(int i = 0; i < num; i++) {
        printf("%d", Data[i]);
        if(i != num - 1) printf(" ");
    }
    return 0;
}

（2）堆排序

?首先將一個無序的序列生成最大堆，從樹的倒數(shù)第二排最右邊開始，下標是節(jié)點總數(shù)/2-1，然后依次遞減1，不斷將以當前下標為根節(jié)點的子樹調整為最大堆

調整過程為下濾

接著不需要將堆頂元素輸出，而是將堆頂元素與當前堆的最后一個元素交換位置，交換完位置后再將大小減1的堆重新調整成最大堆，重復上述過程，原來保存最大堆的數(shù)組就轉換為一個從小到大的序列

/*堆排序建立堆的時候，
相對于之前建立堆是插入，
這個是在一堆無序的數(shù)字上建立
*/
#include <stdio.h>
#include <stdlib.h>
#define MAX_NUM 100005
int Data[MAX_NUM];
void Swap(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
    return;
}
void PercDown(int data[], int root, int num) { //建立最大堆和從最大堆中彈出最大值，核心部分都是下濾
    //相對與之前的最大堆算法，本題特殊之處在于用于存儲最大堆的數(shù)組不是從下標1開始，0做哨兵，而就是從0開始
    int parent, child;
    
    int tmp = data[root];
    //從root開始，遍歷數(shù)組，比較當前值和左右子節(jié)點，若當前值大于左右子節(jié)點，則交換當前值和左右子節(jié)點的值，并重新調整最大堆
    for(parent = root; parent * 2 + 1 < num; parent = child) {
        child = parent * 2 + 1;
        if((child!= num - 1) && (data[child] < data[child + 1])) {
            child++;
        }
        if(tmp >= data[child]) {
            break;
        }
        else {
            data[parent] = data[child];
        }
    }
    data[parent] = tmp;
    return;
}
void HeapSort(int data[], int num) {
    //建立最大堆
    for(int i = num / 2 - 1; i >= 0; i--) {
        PercDown(data, i, num);
    }
    //刪除最大堆頂
    for(int i = num - 1; i > 0; i--) {
        Swap(&data[0], &data[i]);
        PercDown(data, 0, i);
    }
}
int main() {
    int num;
    scanf("%d", &num);
    for(int i = 0; i < num; i++) {
        scanf("%d", &Data[i]);
    }
    HeapSort(Data, num);
    for(int i = 0; i < num; i++) {
        printf("%d", Data[i]);
        if(i != num - 1) {
            printf(" ");
        }
    }
    return 0;
}

（二）插入排序?

（1）簡單插入排序

將序列分為已排和未排，每次從未排中取一個與已排比較直到合適位置后插入，重復上述過程，直到?jīng)]有未排序列

#include <stdio.h>
#include <stdlib.h>
#define MAX_NUM 100005
int Data[MAX_NUM];
void SimpleInsertSort(int data[], int num) {
    for(int i = 1; i < num; i++) {
        int tmp = data[i];  //取出未排序列中第一個元素
        int j = i;
        for(; j > 0 && data[j - 1] > tmp; j--) {    //依次與已排序列從末尾往前比
            data[j] = data[j - 1];  
        }
        data[j] = tmp;  //將未排序列第一個元素插入到已排序列合適位置
    }
    return;
}
int main() {
    int num;
    scanf("%d", &num);
    for(int i = 0; i < num; i++) {
        scanf("%d", &Data[i]);
    }
    SimpleInsertSort(Data, num);
    for(int i = 0; i < num; i++) {
        printf("%d", Data[i]);
        if(i != num - 1) {
            printf(" ");
        }
    }
    return 0;
}

（2）希爾排序

通過將待排序的一組元素按一定間隔分為若干個序列，分別進行插入排序；最終間隔是1

往往用Sedgewick作為增量序列

void ShellSort(int data[], int num) {
    //定義一個增量數(shù)組
    int i;
    int sedgewick[] = {929, 505, 209, 109, 41, 19, 5, 1, 0};

    //在sedgewick序列中找到比num小的增量，因為初始的增量sedgewick[i]不能超過待排序列長度
    for(i = 0; sedgewick[i] >= num; i++)    //在sedgewick序列中找到比num小的增量，因為初始的增量sedgewick[i]不能超過待排序列長度
        ;

    for(int interval = sedgewick[i]; interval > 0; interval = sedgewick[++i]) {
        //插入排序
       //比較難以理解，首先從一個intervel以后開始選擇，因為下標0~intervel-1是分別intervel的第一個（第一個又是已排序列）
        for(int j = interval; j < num; j++) {  
            int tmp = data[j];  //取出未排序列中第一個元素
            int k = j;
            //依次將其已排序元素進行比較
            for(; k >= interval && data[k - interval] > tmp; k -= interval) {   //依次與已排序列從末尾往前比
                data[k] = data[k - interval];
            }
            data[k] = tmp;  //將未排序列的第一個元素插入到已排序列中合適位置
        }
    }
}

（三）交換排序?

（1）冒泡排序

外層循環(huán)從待排序列最后一位往前依次確定，內層循環(huán)從前往后掃描兩兩比較取最大

減少循環(huán)的一個方法是每層循環(huán)設置一個flag，如果從頭至尾掃描循環(huán)都沒有交換，說明當前序列已經(jīng)有序，可以break了

#include <stdio.h>
#define MAX_NUM 100005
#define bool int
#define TRUE 1
#define FALSE 0
int Data[MAX_NUM];
void Swap(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
    return;
}
void BubbleSort(int data[], int num) {
    for(int i = num - 1; i >= 0; i--) {    //依次從下標num - 1開始往前定位
        bool flag = FALSE;  //標記該次循環(huán)中是否發(fā)生交換，若無，說明該序列已經(jīng)有序
        for(int j = 0; j < i; j++) {
            if(data[j] > data[j + 1]) {
                Swap(&data[j], &data[j + 1]);
                flag = TRUE;
            }
        }
        if(flag == FALSE) {
            break;
        }
    }
    return;
}
int main() {
    int num;
    scanf("%d", &num);
    for(int i = 0; i < num; i++) {
        scanf("%d", &Data[i]);
    }
    BubbleSort(Data, num);
    for(int i = 0; i < num; i++) {
        printf("%d", Data[i]);
        if(i != num - 1) {
            printf(" ");
        }
    }
    return 0;
}

（2）快速排序

快速排序的思路是通過分治法，首先取一個pivot基準值，將大于pivot的都移到右邊，小于它的都移到左邊，將一個序列分成兩個序列，然后將這兩個序列分別重復上述操作

具體實現(xiàn)：

首先為了減少時間復雜度，要考究選擇的pivot，方法是將最左邊，最右邊和中間（left + right)/2按最左邊<=中間<=最右邊，因為這樣排序后最左邊必定比中間小，最右邊必定比中間大，將中間的值移動到最右邊倒數(shù)第二個后，比較范圍只用從最左邊下標+1到最右邊下標-2

另一個優(yōu)化是因為遞歸針對較大數(shù)據(jù)還好，但對于較小數(shù)據(jù)就很慢，所以臨設一個cutoff變量，當前序列大小比這個大就用快排，如果小就直接用簡單插入排序

但發(fā)現(xiàn)這個cutoff最小必須設為2，再小就報錯了，目前還沒想出來是為什么

#include <stdio.h>
#define TRUE 1
#define FALSE 0
#define MAX_NUM 100005
typedef int bool;
int Data[MAX_NUM];
int Cutoff = 3;
void Swap(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
    return;
}
/*實現(xiàn)簡單插入排序*/
void SimpleInsertSort(int data[], int left, int right) {
    for(int i = left + 1; i <= right; i++) {
        int tmp = data[i];
        int j = i;
        for(; j > left && data[j - 1] > tmp; j--) {
            data[j] = data[j - 1];
        }
        data[j] = tmp;
    }
    return;
}
/*下面函數(shù)作用是確定快排中主元，將最左邊、最右邊、中間元素調整為
最左邊 <= 中間 <= 最右邊，此時最左邊一定小于中間，最右邊一定大于等于中間，這兩個所以就不用考慮了
將中間的主元放到右邊倒數(shù)第二個位置，下面就只用比較左邊第二個到右邊倒數(shù)第三個位置的范圍就行*/
int CompareThreeNums(int data[], int left, int right) {
    int mid = (left + right) / 2;
    int max = data[left];
    if(data[left] > data[mid]) {
        Swap(&data[left], &data[mid]);
    }
    if(data[left] > data[right]) {
        Swap(&data[left], &data[right]);
    }
    if(data[mid] > data[right]) {
        Swap(&data[mid], &data[right]);
    }
    Swap(&data[mid], &data[right - 1]);
    return data[right - 1];
}
void QuickSortCore(int data[], int left, int right) {
    if(Cutoff <= right - left) {
        int pivot = CompareThreeNums(data, left, right);
        int low = left;
        int high = right - 1;
        while(TRUE) {
                while(data[++low] < pivot) ;
                while(data[--high] > pivot) ;
                if(low < high) {
                    Swap(&data[low], &data[high]);
                }
                else {
                    break;
                }
        }
        Swap(&data[low], &data[right - 1]); //將基準換到正確位置
        QuickSortCore(data, left, low - 1); //對基準左邊序列遞歸
        QuickSortCore(data, low + 1, right);    //對基準右邊序列遞歸
    }
    else {
        SimpleInsertSort(data, left, right); //對序列進行簡單插入排序
    }
    return;
}
void QuickSort(int data[], int num) {
    QuickSortCore(data, 0, num - 1);
    return;
}
int main() {
    int num;
    scanf("%d", &num);
    for(int i = 0; i < num; i++) {
        scanf("%d", &Data[i]);
    }
    QuickSort(Data, num);
    for(int i = 0; i < num; i++) {
        printf("%d", Data[i]);
        if(i != num - 1) {
            printf(" ");
        }
    }
    return 0;
}

（四）歸并排序?

歸并排序的思路類似于快排，不過歸并是通過將待排序列不斷分割到每個序列只剩兩個數(shù)字時排序，然后再兩兩合并實現(xiàn)排序文章來源地址http://www.zghlxwxcb.cn/news/detail-682057.html

①遞歸版本

#include <stdio.h>
#include <stdlib.h>
#define MAX_NUM 100005
int DataToSort[MAX_NUM];
void Merge(int data[], int tmpData[], int leftStart, int rightEnd, int rightStart) {
    int leftEnd = rightStart - 1;
    int tmpStart = leftStart;
    int num = rightEnd - leftStart + 1;
    while(leftStart <= leftEnd && rightStart <= rightEnd) {
        if(data[leftStart] <= data[rightStart]) {
            tmpData[tmpStart++] = data[leftStart++];
        }
        else {
            tmpData[tmpStart++] = data[rightStart++];
        }
    }    
    while(leftStart <= leftEnd) {
        tmpData[tmpStart++] = data[leftStart++];
    }
    while(rightStart <= rightEnd) {
        tmpData[tmpStart++] = data[rightStart++];
    }
    for(int i = 0; i < num; i++, rightEnd--) {
        data[rightEnd] = tmpData[rightEnd];
    }
    return;
}
void MergeSortRecursiveVersionCore(int data[], int tmpData[],int leftStart, int rightEnd) {
    if(leftStart >= rightEnd) {
        return;
    }
    int mid = (leftStart + rightEnd) / 2;
    MergeSortRecursiveVersionCore(data, tmpData, leftStart, mid);
    MergeSortRecursiveVersionCore(data, tmpData, mid + 1, rightEnd);
    Merge(data, tmpData, leftStart, rightEnd, mid + 1);
    return;
}
void MergeSort(int data[], int num) {
    int* tmpData = (int*)malloc(sizeof(int) * num);
    MergeSortRecursiveVersionCore(data, tmpData, 0, num - 1);
    free(tmpData);
    return;
}
int main() {
    int num;
    scanf("%d", &num);
    for(int i = 0; i < num; i++) {
        scanf("%d", &DataToSort[i]);
    }
    MergeSort(DataToSort, num);
    for(int i = 0; i < num; i++) {
        printf("%d", DataToSort[i]);
        if(i != num - 1) {
            printf(" ");
        }
    }
    return 0;
}

②循環(huán)版本?

#include <stdio.h>
#include <stdlib.h>
#define MAX_NUM 100005
int DataToSort[MAX_NUM];
void Merge(int data[], int tmpData[], int leftStart, int rightStart, int rightEnd) {
    int leftEnd = rightStart - 1;
    int tmpStart = leftStart;
    int numElements = rightEnd - leftStart + 1;
    while(leftStart <= leftEnd && rightStart <= rightEnd) {
        if(data[leftStart] <= data[rightStart]) {
            tmpData[tmpStart++] = data[leftStart++];
        }
        else {
            tmpData[tmpStart++] = data[rightStart++];
        }
    }
    while(leftStart <= leftEnd) {
        tmpData[tmpStart++] = data[leftStart++];
    }
    while(rightStart <= rightEnd) {
        tmpData[tmpStart++] = data[rightStart++];
    }
    for(int i = 0; i < numElements; i++, rightEnd--) {
        data[rightEnd] = tmpData[rightEnd];
    }
    return;
}
/*length表示當前有序序列*/
void MergeCirculationSortCore(int data[], int tmpData[], int length, int totalNum) {
    /*i表示當前序列中左開頭*/
    /*下面代碼中傳i， i + length, i + 2 * length - 1等都是坐標*/
    int i;
    for(i = 0; i <= totalNum - 2 * length; i += 2 * length) {    
        Merge(data, tmpData, i, i + length, i + 2 * length - 1);
    }
    /*如果剩余的序列已經(jīng)小于等于兩個length但依然比一個length長*/
    if(i + length < totalNum) {
        Merge(data, tmpData, i, i + length, totalNum - 1);
    }
    /*如果剩余的序列已經(jīng)不足一個length*/
    else {
        for(int j = i; j < totalNum; j++) {
            tmpData[j] = data[j];
        }
    }
    return;
}
void MergeCirculationSort(int data[], int num) {
    int length = 1;
    while(length < num) {
        int* tmpData = (int*)malloc(sizeof(int) * num);
        /*第一次先對按length長度的序列排序*/
        MergeCirculationSortCore(DataToSort, tmpData, length, num);
        length *= 2;
        /*第二次對之前l(fā)ength長度的2倍的序列歸*/
        MergeCirculationSortCore(tmpData, data, length, num);
        length *= 2;    
        free(tmpData);    
    }
    return;
}
int main() {
    int num;
    scanf("%d", &num);
    for(int i = 0; i < num; i++) {
        scanf("%d", &DataToSort[i]);
    }
    MergeCirculationSort(DataToSort, num);
    for(int i = 0; i < num; i++) {
        printf("%d", DataToSort[i]);
        if(i != num - 1) {
            printf(" ");
        }
    }   
    return 0;
}

到了這里，關于浙大數(shù)據(jù)結構之09-排序1 排序的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！