【数据结构--排序】

一、排序概述

1.1、排序的相关定义

1. 排序： 就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。为了查找方便，通常希望计算机中的表是按关键字有序的。排序的确切定义如下：
   输入：n个记录$R_1,R_2,...,R_n$，对应的关键字为$K_1,K_2,...,K_n$。
   输出：输入序列的一个重排$R_1^{{}^{\prime }},R_2^{{}^{\prime }},...,R_n^{{}^{\prime }}$，使得$K_1^{{}^{\prime }}<=K_2^{{}^{\prime }}<=K_3^{{}^{\prime }}<=...K_n^{{}^{\prime }}$其中“<=”可换成其他比较大小的符号。
2. 排序的稳定性： 假设$k_i=k_j(1<=i<=n,1<=j<=n,i!=j)$，且在排序前的序列中$R_i$领先于$R_j$，如果在排序后，$R_i$仍然领先于$R_j$，则所用的排序方法是稳定的，反之不稳定。
3. 内部排序和外部排序： 内部排序是在排序整个过程中，待排序的所有记录全部被放置在内存中。外部排序是由于排序的记录数量太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行。

内部排序算法的性能取决于算法的时间复杂的和空间复杂度，时间复杂度一般是由比较时间和移动次数决定的。

1.2、排序用到的结构与函数

1. 排序常用的顺序表结构

#define MaxSize 10  //用于要排序的数组中元素个数最大值，可根据需求进行修改
typedef struct{
     int R[MaxSize];//用于存储待排序的数组
     int length;//用于记录顺序表的长度
}SqList;
1
2
3
4
5

2. 排序常用的数组中两数交换，将其写为函数，方便调用

void swap(SqList *L, int i, int j){
    int temp = L->R[i];
    L->R[i] = L->R[j];
    L->R[j] = temp;
}
//或不借助temp
void swap(SqList *L, int i, int j){
    L->R[i] = L->R[i] + L->R[j];
    L->R[j] = L->R[i] - L->R[j];
    L->R[i] = L->R[i] - L->R[j];
}
1
2
3
4
5
6
7
8
9
10
11

二、常见排序算法

2.1、冒泡算法（交换顺序）

（1）算法

冒泡排序的基本思想是： 从后往前（或从前往后）两两比较相邻元素的值，若为逆序（小的在前为证序，大的在前为逆序），则进行交换，直到序列比较完。第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置），关键字最小的元素就像气泡一样逐渐向上漂浮，直至水面（或关键字最大的元素就像石头一样下沉，直至水底）。下一趟冒泡时，前一趟确定的最小元素不再参与比较，每趟冒泡的结果是把序列中的最小元素（或最大元素）放到序列的最终位置，这样最多做n-1（n为序列中的元素个数）趟冒泡就能把所有元素排好序。

void BubbleSort(SqList *L){
    int i, j;
    bool flag = true;//表示本趟冒泡是否发生的标志
    for(i = 0; i < L->length-1; i++){
        flag = false;
        //一趟冒泡过程
        for(j = L->length-1; j > i; j--)
            //从后往前，若为逆序，则进行交换
            if(L->R[j-1] > L->R[j]){
                swap(&L,j,j-1);
                flag = true;
            }
    }
    if(flag == false){
        return;//本趟遍历后没有修改flag的值，说明序列已经有序，不需要再进行冒泡
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

（2）性能分析

• 稳定性：稳定
• 空间效率：空间复杂度为$O(1)$；
• 时间效率：当初始序列有序时，比较次数为n-1，元素移动次数为0，最好情况下的时间复杂度就为$O(n)$；当初始序列为逆序时，需要进行n-1趟排序，每趟排序要进行n-i次比较，每次比较后都必须进行n-i次移动，则：$$比较次数=交换次数=(n-1)+(n-2)+(n-3)+...+1=\frac{n(n-1)}{2}$$，所以最坏时间复杂度为$O(n^2)$，平均时间复杂度为$O(n^2)$。

2.2、简单选择排序

（1）算法

简单选择排序（Simple Selection Sort）就是通过n-i次关键字的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1<i<n）个记录进行交换。

void SelectSort(SqList *L){
    for(int i=0; i < L->length-1; i++){
        int min = i;//记录最小元素所在位置
        for(int j = i+1; j < L->length; j++){
            if(L->R[j] < L->R[min]){
                min = j;//更新最小元素的位置
            }
        }
        if(min != i){
            swap(&L, i,min);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

（2）性能分析

• 稳定性：不稳定
• 空间效率：空间复杂度为$O(1)$；
• 时间效率：从代码不难看出，在简单选择排序过程中，元素比较次数为$$比较次数=(n-1)+(n-2)+...+1=\frac{n(n-1)}{2}$$交换次数满足$$交换次数<n-1$$则时间复杂度为$O(n^2)$。

2.3、直接插入排序

（1）算法

直接插入排序（Staright Insertion Sort）的基本操作是将一个待排序的记录按其关键字大小插入到前面已经排好的子序列中，直到全部记录插入完成。

//不带哨兵的直接插入排序
void InsertionSort(SqList *L){
    int temp;
    for(int i = 1; i <L->length; i++){
        if(L->R[i] < L->R[i-1]){//若记录关键字小于前驱
            temp = L->R[i];
            for(int j = i-1; j >= 0 && L->R[j] > temp; --j){
                L->R[j+1] = L->R[j];
            }
            L->R[j+1] = temp;
        }
    }
}
//带哨兵的直接插入排序
void InsertionSort(SqList *L){
    for(int i = 2; i < L->length; i++){
        if(L->R[i] < L->R[i-1]){
            L->R[0] = L-<R[i];//下标为0处设置哨兵，免去后续对越界的判断
            for(int j = i-1; L->R[j] > L->R[0]; --j){
                L->R[j+1] = L->R[j];
            }
            L->R[j+1] = L->R[0];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

示例分析：
初始序列为 { 49 , 38 , 65 , 97 , 76 , 13 , 27 , 49 } \{49,38,65,97,76,13,27,49\} {49,38,65,97,76,13,27,49}

（2）性能分析

• 稳定性：稳定
• 空间效率：空间复杂度为$O(1)$；
• 时间效率：在排序过程中，向有序子表中逐个插入元素的操作进行了n-1趟，每趟操作都分为比较和移动元素，最好情况下，每趟比较1次，移动0次，时间复杂度为$O(n)$，最坏情况为逆序，时间复杂度为$O(n^2)$。

2.4、折半插入排序

（1）算法

折半插入排序是在直接插入排序的基础上做的优化，针对的是在有序子表中查找插入位置时的操作，利用折半查找来进行。

void BinaryInsertSort(SqList *L){
    int left, right, mid;
    for(int i=2; i <= L->length; i++){
        L->R[0] = L->R[i];
        left = 1;
        right = i - 1;
        while(left <= right){
            mid = (left + right)/2;
            if(L->R[mid] > L->R[0]){
                right = mid- 1;
            }else{
                left = mid + 1;
            }
            for(int j = i-1; j >= right+1; --j){
                L->R[j+1] = L->R[j];//统一后移元素，空出位置
            }
            L->R[right+1] = L->R[0];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

（2）性能分析

• 稳定性：稳定
• 空间效率：空间复杂度为$O(1)$；
• 时间效率：时间复杂度为$O(n^2)$

2.5、希尔排序

（1）算法

希尔排序是对直接插入排序进行改进得到的，又称缩小增量排序。其基本思想是：先将待排序列分割成若干形如$L[i,i+d,i+2d,...,i+kd]$的“特殊”子表，即把相隔某个增量的记录组成一个子表，对各个子表分别进行直接插入排序，缩小增量d，重复上述过程，直到d=1为止。

仅适用于顺序表存储。

示例分析：
初始序列为 { 49 , 38 , 65 , 97 , 76 , 13 , 27 , 49 } \{49,38,65,97,76,13,27,49\} {49,38,65,97,76,13,27,49}，$n=8$
①第一次：$d_1=\frac{n}{2}=4$

各个子表进行插入排序

第一次排序的结果为：

②第二次：$d_2=\frac{d_1}{2}=2$

各个子表进行插入排序

第二次排序的结果为：

③第三次：$d_3=\frac{d_2}{2}=1$

进行直接插入排序，结果为：

void ShellSort(SqList *L){
    int step;//增量
    for(step = n/2; step > 0; step = step / 2){
        for(int i = 0; i < step; i++)//i是子表的编号
            for(int j = i + step; j < n; j = j + stap){
                if(L->R[j] < L->R[j-step]){
                    int temp = L->R[j];
                }
                for(int k = j - step; K>=0 && L->R[K] > temp; k = k - step){
                    L->R[k+step] = L->R[k];
                }
                L->R[k+step] = temp;
            }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

（2）性能分析

• 稳定性：不稳定
• 空间效率：空间复杂度为$O(1)$
• 时间效率：无法确切计算具体时间复杂度

2.6、堆排序

（1）算法

堆排序（Heap Sort）是对简单选择排序的一种改进。
1. 堆的定义
堆是具有下列性质的完全二叉树：
每个结点的值都大于或等于其左右孩子结点的值，称为大根堆；
每个结点的值都小于等于其左右孩子结点的值，称为小根堆。

2. 堆排序
堆排序的思路很简单：首先将存放在$L[\mathrm{1...}n]$中的n个元素建成初始堆，由于堆本身的特点（以大根堆为例），堆顶元素就是最大值。输出堆顶元素后，通常将堆底元素送入堆顶，此时根结点已不满足大根堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大根堆的性质，在输出堆顶元素，如此重复，直到堆中只剩一个元素为止。可见堆排序需要解决两个问题：①如何将无序的序列构造成初始堆（关键）②输出对顶元素后，如何将剩余元素调整为新的堆。

以大根堆为例，每一次将堆顶元素加入有序子序列，即把堆顶元素放入序列最右侧。再将前面所有的元素进行堆调整，经过调整之后，剩余元素中最大的元素又会到堆顶，再将堆顶元素与当前序列的堆底元素互换，重复上述操作，直至前面元素只有1个，因为只有一个，不用再进行调整，它就是最小的，这样，经过大根堆排序的序列呈现非递减趋势。

//建大根堆
void BuildMaxHeap(int A[], int len){
    //从后往前调整所有非叶子结点
    for(int i = len/2; i > 0; i--){
        Headadjust(A,i,len);
    }
}
//大根堆堆调整
void Headadjust(int A[], int k, int len){
    A[0] = A[K];//A[0]暂存以k为根结点时的值
    for(int i = 2*k; i <= len; i *= 2;){
        if(i < len && A[i] < A[i+1])//比较根结点k的左右孩子大小
            i++;//若右孩子大于左孩子，则将i更新为右孩子得到下标
        if(A[0] >= A[i])    break;//根结点的值大于等于孩子中最大的值，说明符合大根堆性质
        else{
            A[K] = A[i];//孩子的值大于根结点的话，就把大值给根结点
            k = i;//更新根结点的位置为原本孩子的位置，以便向下继续遍历
        }
    }
    A[k] = A[0];//把之前暂存进A[0]的根结点值给孩子，以实现根结点与孩子值的互换
}
//大根堆排序
void HeapSort(A[], int len){
    //首先建立大根堆
    BuildMaxHeap(A, len);
    //len-1趟交换和建堆过程
    for(int i = len; i > 1; i--){
        swap(A[i],A[1]);//把堆顶元素加入序列
        Headadjust(A,1,i-1);//将剩余元素整理成大根堆
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

（2）性能分析

• 稳定性：不稳定
• 空间效率：空间复杂度为$O(1)$
• 时间效率：建堆时间复杂度为$O(n)$，排序时间复杂度为$O(lo{g}_{2}n)$，因此总的时间复杂度为$O(nlo{g}_{2}n)$。

2.7、归并排序

（1）算法

归并排序（Merge Sort）与上述基于交换、选择等排序的思想不一样，“归并”的含义是将两个或多个以上的有序表组成一个新的有序表。假定排序表含有n个记录，则可将其视为n个有序的子表，每个子表的长度为1，然后两两归并，得到[n/2]个长度为2或1的有序表；继续两两归并，如此重复，直至合并成一个长度为n的有序表为止，这种排序叫做2路归并排序。
示例：

Merge()的功能是将前后相邻的两个有序表归并为一个有序表。设两段有序表A[low…mid],A[mid+1…high]存放在同一顺序表的相邻位置，先将它们复制到辅助数组B中。每次从对应数组B中的两段取出一个记录进行关键字的比较，将较小者放入A中，当数组B中有一段的下标超过其对应的表长（即该段所有元素都已复制到A中）时，将另一段中的剩余部分直接复制到A中。算法如下：

int *B = (int *)malloc(n*sizeof(int));//构造辅助数组B

void Merge(intA[], int low, int mid, int high){
    int i;
    int j;
    int k;
    for(k = low; k <= high; k++){
        B[K] = A[K];//将A中所有元素复制到B中
    }
    for(i = low, j = mid + 1, k = i;i <= mid && j <= high; k++){
        if(B[i] <= B[j])
            A[K] = B[i++];//将较小值复制到A中
        else
            A[k] = B[j++];
    }
    while(i <= mid)    A[k++] = B[i++];//若第一个表未检测完，则直接将剩余部分复制进A
    while(j <= high)    A[k++] = B[j++];//若第二个表未检测完，则直接将剩余部分复制进A
}
//
void MergeSort(A[], int low, int high){
    if(low < high)
        int mid = (low + high)/2;//从中间划分为两部分
        MergeSort(A,low,mid);//对左半部分进行归并排序
        MergeSort(A,mid+1,high);//对右半部分进行归并排序
        Merge(A,low,mid,high);//归并
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

（2）性能分析

• 稳定性：稳定
• 空间效率：空间复杂度为$O(n)$。
• 时间效率：每趟归并的时间复杂度为$O(n)$，共需进行$lo{g}_{2}n$次归并，所以算法总的时间复杂度为$O(nlo{g}_{2}n)$。

2.8、快速排序

（1）算法

快速排序（Quick Sort）是对冒泡排序的优化。冒泡排序通过不断比较和交换来实现排序，不过其相比于冒泡排序，增大了比较和交换的距离，将关键字较大的记录从前面直接移动到后面，关键字较小的记录从后面直接移动到前面，从而减少了总的比较次数和交换次数。
基本思想为：在待排序表L[1…n]中任取一个元素pivot作为枢轴（或基准，通常取首元素），通过一趟排序将待排记录分割成独立的两部分L[1…k-1]和L[k+1…n]，使得L[k+1…n]中所有元素均大于等于pivot，L[1…k-1]中的所有元素均小于等于pivot，则pivot放在了其最终位置上L(k)，这个过程称为一次划分。然后分别递归地对两个子表重复上述过程，直至每部分中只有一个元素或者为空为止，即所有的元素放在了其最终位置上。
示例：
初始序列为： { 49 , 38 , 65 , 97 , 76 , 13 , 27 , 49 } \{49,38,65,97,76,13,27,49\} {49,38,65,97,76,13,27,49}
设两个指针i和j，初值分别为low和high；
①选择第一个元素49作为枢轴

j从后往前搜索比49小的元素，并移动到左边，即i指的位置。搜索到的第一个比49小的元素为27，将其放到i指向的位置。

此时原本27的位置就空出来了，i从前往后搜索大于等于49的元素，第一个搜索到的元素为65，则将65放到j指向的位置（即原本27空出来的位置）。

j继续从后往前搜索，找到了13，将13放到拿走65后留下的空位处。

i继续从前往后搜索，找到了97，将97放到拿走13后留下的空位处。

现在i == j了，将枢轴49放到i 指向的位置，而此处即49最终的位置。
经过一趟划分，序列变成了两个部分：

按照同样的方法对各子序列进行排序，直至待排序列中的元素小于等于1，整体排序就完成。

//划分，确定枢轴位置
void Partiion(int A[], int low, int high){
    int pivot = A[low];//用第一个元素作枢轴
    while(low < high){
        while(low < high && A[high] >= pivot){
            --high;
        }
        A[low] = A[high];//比枢轴小的元素放到左边
        while(low < high && A[low] < pivot){
            ++low;
        }
        A[high] = A[low];//比枢轴大的元素放到右边
    }
    A[low] = pivot;//枢轴元素放到最终位置
    return low;//返回枢轴的最终位置
}
//快速排序
void QuickSort(int A[], int low, int high){
    if(low < high){
        int pivotpos = Partition(A,low,high);//划分
        QuickSort(A,low,pivotpos-1);//对左半部分进行递归操作
        QuickSort(A,pivotpos+1,high);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

（2）性能分析

• 稳定：不稳定
• 空间效率：由于快速排序是递归的，需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量与递归调用深度一致，最好情况下为：$O(lo{g}_{2}n)$，最坏情况下为$O(n)$，平均空间复杂度为：$O(lo{g}_{2}n)$
• 时间效率：最坏情况下的时间复杂度为：$O(n^2)$，最好情况下，时间复杂度为：$O(nlo{g}_{2}n)$

三、各种排序算法的比较