---

2.3 交换排序

交换排序基本思想：

所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置

交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动

2.3.1 冒泡排序

前面在算法题中我们已经接触过冒泡排序的思路了，冒泡排序是一种最基础的交换排序。之所以叫做冒泡排序，因为每一个元素都可以像小气泡一样，根据自身大小一点一点向数组的一侧移动。

代码实现：

void BubbleSort(int* a, int n) 
{int exchange = 0;for (int i = 0; i < n; i++){for (int j = 0; j <n-i-1 ; j++){if (a[j] > a[j + 1]) {exchange = 1;swap(&a[j], &a[j + 1]);}}if (exchange == 0) {break;}}
}

冒泡排序的特性总结

1. 时间复杂度：O(N² )
2. 空间复杂度：O(1)

---

2.3.2 快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

快速排序实现主框架：

//快速排序
void QuickSort(int* a, int left, int right) 
{if (left >= right) {return;}//_QuickSort用于按照基准值将区间[left,right)中的元素进行划分int meet = _QuickSort(a, left, right);QuickSort(a, left, meet - 1);QuickSort(a, meet + 1, right);
}

将区间中的元素进行划分的 _QuickSort 方法主要有以下几种实现方式：

2.3.2.1 hoare版本

算法思路 ：

1. 创建左右指针，确定基准值

2. right从右向左找出比基准值小的数据，left从左向右找出比基准值大的数据，左右指针数据交换，进入下次循环

问题1：为什么跳出循环后right位置的值一定不大于key？

当 left > right 时，即right走到left的左侧，而left扫描过的数据均不大于key，因此right此时指向的数据一定不大于key

问题2：为什么left 和 right指定的数据和key值相等时也要交换？

相等的值参与交换确实有一些额外消耗。实际还有各种复杂的场景，假设数组中的数据大量重复时，无法进行有效的分割排序。

key是基准值

---

例如：

6 1 2 7 9 3

key指向6，left指向1，right指向3

left从左向右找出比基准值大的数据，right从右向左找出比基准值小的数据，左右指针数据交换，进入下次循环

left指向7，right指向3

交换left和right

left指向的数据7变成数据3，right指向的数据3变成数据7

---

6 1 2 3 9 7

key指向6，left指向3，right指向7

left从左向右找出比基准值大的数据，right从右向左找出比基准值小的数据，左右指针数据交换，进入下次循环

left指向9，right指向3

此时left>right

left > right的时候，right和基准值key交换

交换key和right的数据

3 1 2 6 9 7

然后返回基准值6

代码实现：

Sort.h

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include<stdlib.h>
#include<time.h>//打印
void PrintArr(int* arr, int n);
//快速排序
//hoare版本
void QuickSort(int* arr, int left, int right);

Sort.c

#include"Sort.h"//打印
void PrintArr(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}//交换
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}//快速排序找基准值
int _QuickSort(int* arr, int left, int right)
{int keyi = left;++left;while (left <= right)//left和right相遇的位置的值比基准值要大{//right找到比基准值小的while (left <= right && arr[right] > arr[keyi]){right--;//right从右往左找比基准值keyi要小的，当前位置不满足就向前一位}//left找到比基准值大的while (left <= right && arr[left] < arr[keyi]){left++;//left从左往右找比基准值keyi要大的，当前位置不满足就向后一位}//right和left互相交换//因为left找到比基准值大的，right找到比基准值小的//left比right小的时候，自然要交换数据if (left <= right){Swap(&arr[left++], &arr[right--]);}}//left > right的时候，right和基准值keyi交换Swap(&arr[keyi], &arr[right]);return right;//返回基准值
}//快速排序
void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}//[left,right]--->找基准值keyiint keyi = _QuickSort(arr, left, right);//左子序列：[left,keyi-1]QuickSort(arr, left, keyi - 1);//右子序列：[keyi+1,right]QuickSort(arr, keyi + 1, right);
}

test.c

#include"Sort.h"int main()
{int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };int n = sizeof(a) / sizeof(int);printf("排序前：");PrintArr(a, n);QuickSort(a, 0, n - 1);printf("排序后：");PrintArr(a, n);return 0;
}

---

2.3.2.2 挖坑法

思路：

创建左右指针。首先从右向左找出比基准小的数据，找到后立即放入左边坑中，当前位置变为新的坑，然后从左向右找出比基准大的数据，找到后立即放入右边坑中，当前位置变为新的坑，结束循环后将最开始存储的分界值放入当前的坑中，返回当前坑下标（即分界值下标）

代码：

Sort.h

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include<stdlib.h>
#include<time.h>//打印
void PrintArr(int* arr, int n);
//快速排序
//挖坑法
void QuickSort(int* arr, int left, int right);

Sort.c

#include"Sort.h"//打印
void PrintArr(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}//快速排序找基准值
//挖坑法
int _QuickSort2(int* arr, int left, int right)
{int hole = left;//找到坑位int key = arr[hole];//存储第一个坑位的值while (left < right)//left = right就跳出循环{while (left < right && arr[right] > key)//找到arr[right] < key的right{--right;}arr[hole] = arr[right];//填坑hole = right;//确定新的坑位while (left < right && arr[left] < key)//找到arr[left] > key的left{++left;}arr[hole] = arr[left];//填坑hole = left;//确定新的坑位}arr[hole] = key;//最后的坑位放上初始值return hole;//返回基准值
}//快速排序
void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}//[left,right]--->找基准值keyiint keyi = _QuickSort(arr, left, right);//左子序列：[left,keyi-1]QuickSort(arr, left, keyi - 1);//右子序列：[keyi+1,right]QuickSort(arr, keyi + 1, right);
}

test.c

#include"Sort.h"int main()
{int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };int n = sizeof(a) / sizeof(int);printf("排序前：");PrintArr(a, n);QuickSort(a, 0, n - 1);printf("排序后：");PrintArr(a, n);return 0;
}

当然这里会有一点小问题的。比如数据是升序的时候，基准值找起来会有点问题。但因为这里是初阶数据结构，所以先不讨论基准值。后面的高阶数据结构里面会讲三数取中。

---

2.3.2.3 lomuto前后指针

创建前后指针，从左往右找比基准值小的进行交换，使得小的都排在基准值的左边。

思路：

定义两个变量prev和cur

cur指向位置的数据和key值比较

若arr[cur] < arr[keyi]，prev往后走一步并和cur交换

若arr[cur] > arr[keyi]，cur继续往后

arr[cur]越界后，将key里的值和arr[prev]的值互换。

代码：

Sort.h

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include<stdlib.h>
#include<time.h>//打印
void PrintArr(int* arr, int n);
//快速排序
//lomuto前后指针法
void QuickSort(int* arr, int left, int right);

Sort.c

#include"Sort.h"//打印
void PrintArr(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}//交换
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}//快速排序找基准值
//lomuto前后指针法
int _QuickSort3(int* arr, int left, int right)
{int prev = left, cur = left + 1;int keyi = left;while (cur <= right)//cur > right就说明越界了{if (arr[cur] < arr[keyi] && ++prev != cur)//若arr[cur] < arr[keyi]，prev往后走一步并和cur交换{Swap(&arr[cur], &arr[prev]);}cur++;//若arr[cur] > arr[keyi]，cur继续往后}Swap(&arr[keyi], &arr[prev]);//arr[cur]越界后，将key里的值和arr[prev]的值互换。return prev;//返回基准值
}//快速排序
void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}//[left,right]--->找基准值keyiint keyi = _QuickSort(arr, left, right);//左子序列：[left,keyi-1]QuickSort(arr, left, keyi - 1);//右子序列：[keyi+1,right]QuickSort(arr, keyi + 1, right);
}

test.c

#include"Sort.h"int main()
{int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };int n = sizeof(a) / sizeof(int);printf("排序前：");PrintArr(a, n);QuickSort(a, 0, n - 1);printf("排序后：");PrintArr(a, n);return 0;
}

快速排序特性总结：

1. 时间复杂度：O(nlogn)
2. 空间复杂度：O(logn)

---

2.3.2.4 非递归版本

非递归版本的快速排序需要借助数据结构：栈

思路：

假设我们初始要排序的数是：5 3 9 6 2 4

经过一轮快速排序后，找到的基准值是6，也就是keyi=3

通过一轮快速排序后，接下来要排序的数是2 3 4 5 6 9

---

如果left=0，right=5，keyi=3

左区间：[left,keyi-1] [0,2]

右区间：[keyi+1,right] [4,5]

先把右区间的right：5入栈，然后把右区间的left：4入栈

然后把左区间的right：2入栈，然后把左区间的left：0入栈

---

此时栈里面是：0 2 4 5

---

然后出栈两次，取到left=0，right=2

我们对下标为0-2的数找基准值

找到基准值keyi=0

---

此时left=0，right=2，keyi=1

左区间：[left,keyi-1] [0,-1] 非有效区间，不入栈

右区间：[keyi+1,right] [1,2]

先把右区间的right：2入栈，然后把右区间的left：1入栈

---

此时栈里面是：1 2 4 5

---

然后出栈两次，取到left=1，right=2

我们对下标为1-2的数找基准值

找到基准值keyi=1

---

此时left=1，right=2，keyi=1

左区间：[left,keyi-1] [1,0] 非有效区间，不入栈

右区间：[keyi+1,right] [2,2] 非有效区间，不入栈

---

此时栈里面是：4 5

---

然后出栈两次，取到left=4，right=5

我们对下标为4-5的数找基准值

找到基准值keyi=4

---

此时left=4，right=5，keyi=4

左区间：[left,keyi-1] [4,3] 非有效区间，不入栈

右区间：[keyi+1,right] [5,5] 非有效区间，不入栈

---

此时排完序了，是2 3 4 5 6 9

我们销毁函数栈。

代码实现：

Sort.h

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include<stdlib.h>
#include<time.h>
#include <stdbool.h>
#include <assert.h>//打印
void PrintArr(int* arr, int n);
//非递归版本快排
//--借助数据结构--栈
void QuickSortNonR(int* arr, int left, int right);

Sort.c

#include"Sort.h"//打印
void PrintArr(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}//定义栈的结构
typedef int STDataType;
typedef struct Stack
{STDataType* arr;int capacity;     //栈的空间大小int top;          //栈顶
}ST;//栈的初始化
void STInit(ST* ps)
{assert(ps);ps->arr = NULL;ps->capacity = ps->top = 0;
}//栈顶---入数据，出数据
//入数据
void StackPush(ST* ps, STDataType x)
{assert(ps);//1.判断空间是否足够if (ps->capacity == ps->top){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空间足够ps->arr[ps->top++] = x;
}//判断栈是否为空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//栈顶出数据
void StackPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));--ps->top;
}//取栈顶元素
STDataType StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}//栈的销毁
void STDestroy(ST* ps)
{assert(ps);if (ps->arr)free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;
}//非递归版本快排
//--借助数据结构--栈
void QuickSortNonR(int* arr, int left, int right)
{ST st;//创建栈STInit(&st);//栈的初始化StackPush(&st, right);//栈顶入数据StackPush(&st, left);//栈顶入数据while (!StackEmpty(&st))//栈不为空就进入循环{//取栈顶元素---取两次int begin = StackTop(&st);StackPop(&st);//栈顶出数据int end = StackTop(&st);StackPop(&st);//栈顶出数据//[begin,end]---找基准值//双指针法int prev = begin;int cur = begin + 1;int keyi = begin;while (cur <= end){if (arr[cur] < arr[keyi] && ++prev != cur)//这里<和<=一样{Swap(&arr[cur], &arr[prev]);}cur++;}Swap(&arr[keyi], &arr[prev]);//上面循环结束说明cur越界了keyi = prev;//根据基准值keyi划分左右区间//左区间：[begin,keyi-1]//右区间：[keyi+1,end]if (keyi + 1 < end){StackPush(&st, end);//右区间入栈StackPush(&st, keyi + 1);//左区间入栈}if (keyi - 1 > begin){StackPush(&st, keyi - 1);//右区间入栈StackPush(&st, begin);//左区间入栈}}STDestroy(&st);//销毁栈
}

test.c

#include"Sort.h"int main()
{int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };int n = sizeof(a) / sizeof(int);printf("排序前：");PrintArr(a, n);QuickSortNonR(a, 0, n - 1);printf("排序后：");PrintArr(a, n);return 0;
}

---

2.4 归并排序

归并排序算法思想：

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

思路：

数据：10 6 7 1 3 9 4（7个元素，下标0-6）

---

定义left，right，mid三个变量

left指向下标0的元素

right指向下标6的元素

mid=(left+right)/2

---

[left,mid]：10 6 7 1

[mid+1,right]：3 9 4

---

然后可以继续像上面这样分，直到全部分成一个一个的数据。

递归的话也是递归到这个时候结束，然后往上返回。

那么，对于10 6这两个数字组成的数组，我们怎么把他排序成6 10呢？

---

left指向下标0的元素

right指向下标1的元素

mid=(left+right)/2=0

---

[left,mid]：[0,0] 10

[mid+1,right]：[1,1] 6

其他几个数据也一样

然后我们新创建一个数组来存放这些数：6 10， 1 7， 3 9， 4

然后往上返回。

然后我们新创建一个数组来存放这些数：6 10 1 7， 3 9 4

然后往上返回。

然后把tmp中的数据拷贝回arr中

销毁tmp

代码：

Sort.h

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include<stdlib.h>
#include<time.h>
#include <stdbool.h>
#include <assert.h>//打印
void PrintArr(int* arr, int n);
//归并排序
void MergeSort(int* arr, int n);

Sort.c

#include"Sort.h"//打印
void PrintArr(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}//归并排序
void _MergeSort(int* arr, int left, int right, int* tmp)
{if (left >= right)//分解到只有一个数据的时候就结束了{return;}int mid = (left + right) / 2;//中间下标//[left,mid] [mid+1,right]//不断二分_MergeSort(arr, left, mid, tmp);_MergeSort(arr, mid + 1, right, tmp);//合并//[left,mid] [mid+1,right]//表示两个区间int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int index = begin1;//定义tmp数组的下标while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2])//比较arr[begin1] 和 arr[begin2]的大小{tmp[index++] = arr[begin1++];//先往tmp里面插入小的}else {tmp[index++] = arr[begin2++];//然后往tmp里面插入大的}}//跳出循环：要么begin1越界  要么begin2越界while (begin1 <= end1)//begin2越界，begin1没有越界{tmp[index++] = arr[begin1++];//继续插入}while (begin2 <= end2)//begin1越界，begin2没有越界{tmp[index++] = arr[begin2++];}//[left,mid] [mid+1,right]//把tmp中的数据拷贝回arr中for (int i = left; i <= right; i++){arr[i] = tmp[i];}
}void MergeSort(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);//合并的放在新创建的新数组里，大小是原来数组的空间_MergeSort(arr, 0, n - 1, tmp);free(tmp);//使用完了要释放掉空间
}

test.c

#include"Sort.h"int main()
{int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };int n = sizeof(a) / sizeof(int);printf("排序前：");PrintArr(a, n);MergeSort(a, n);printf("排序后：");PrintArr(a, n);TestOP();return 0;
}

归并排序特性总结：

1. 时间复杂度：O(nlogn)
2. 空间复杂度：O(n)

---

2.5 测试代码：排序性能对比

// 测试排序的性能对比
void TestOP() 
{ srand(time(0)); const int N = 100000; int* a1 = (int*)malloc(sizeof(int)*N); int* a2 = (int*)malloc(sizeof(int)*N); int* a3 = (int*)malloc(sizeof(int)*N); int* a4 = (int*)malloc(sizeof(int)*N); int* a5 = (int*)malloc(sizeof(int)*N); int* a6 = (int*)malloc(sizeof(int)*N); int* a7 = (int*)malloc(sizeof(int)*N); for (int i = 0; i < N; ++i) { a1[i] = rand(); a2[i] = a1[i]; a3[i] = a1[i]; a4[i] = a1[i]; a5[i] = a1[i]; a6[i] = a1[i];a7[i] = a1[i]; } int begin1 = clock(); InsertSort(a1, N); int end1 = clock(); int begin2 = clock(); ShellSort(a2, N); int end2 = clock(); int begin3 = clock(); SelectSort(a3, N); int end3 = clock(); int begin4 = clock(); HeapSort(a4, N); int end4 = clock(); int begin5 = clock(); QuickSort(a5, 0, N-1); int end5 = clock(); int begin6 = clock(); MergeSort(a6, N); int end6 = clock(); int begin7 = clock(); BubbleSort(a7, N); int end7 = clock();printf("InsertSort:%d\n", end1 - begin1); printf("ShellSort:%d\n", end2 - begin2);printf("SelectSort:%d\n", end3 - begin3); printf("HeapSort:%d\n", end4 - begin4); printf("QuickSort:%d\n", end5 - begin5); printf("MergeSort:%d\n", end6 - begin6); printf("BubbleSort:%d\n", end7 - begin7); free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); free(a7); 
} 

对于上面程序的测试结果：（单位：ms）

InsertSort:3816
ShellSort:13
SelectSort:4253
HeapSort:15
QuickSort:9
MergeSort:12
BubbleSort:22812

---

2.6 非比较排序

2.6.1 计数排序

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：

1. 统计相同元素出现次数

2. 根据统计的结果将序列回收到原来的序列中

思路：

例如：{6，1，2，9，4，2，4，1，4}共9个数

1. 统计相同元素出现次数

6出现1次，1出现2次，2出现2次，9出现1次，4出现3次

2. 根据统计的结果将序列回收到原来的序列中

定义一个i来遍历，i表示数组内元素

i先到0的位置，里面没有数据，不打印

然后到1的位置，里面有2，打印2次

依次类推

最后打印结果：1 1 2 2 4 4 4 6 9

---

新数组的大小怎么确定？

利用原数组中最大的值来确定。创建max+1个空间的数组。

但这就会出现问题：比如有负数怎么办？比较{3, 4, 10000}呢?

如果把负数变成正数，取绝对值呢？也不行。因为正负数绝对值一样的情况下无法区分正负数。

那如果我们把负数统一加一个正数，让他变成整数呢？

我们可以让count=max-min+1

对于{-5，-5，9，5，1}

count=9-（-5）+1=15

创建数组，数组大小为15，下标为0-14

-5放在数组下标为0的位置中，这个位置元素为2

依此类推，下标-5就是原来的元素，这些元素和下标形成了映射关系。

代码：

Sort.h

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include<stdlib.h>
#include<time.h>
#include <assert.h>
#include <stdbool.h>
#include <memory.h>//打印
void PrintArr(int* arr, int n);//计数排序
void CountSort(int* arr, int n);

Sort.c

#include "Sort.h"//打印
void PrintArr(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}//计数排序
void CountSort(int* arr, int n)
{//根据最大值最小值确定数组大小int max = arr[0], min = arr[0];for (int i = 1; i < n; i++){if (arr[i] > max){max = arr[i];}if (arr[i] < min){min = arr[i];}}int range = max - min + 1;//确定数组元素个数int* count = (int*)malloc(sizeof(int) * range);//创建数组//判断不为空if (count == NULL){perror("malloc fail!");exit(1);}//初始化count数组中所有的数据为0memset(count, 0, range * sizeof(int));//count的大小是range//例如{100，101，109，105，101，105}//min = 100，arr[i] - min就是count里面的下标//统计数组中每个数据出现的次数for (int i = 0; i < n; i++){count[arr[i] - min]++;//这里的++是为了把次数放进去}//取count中的数据，往arr中放int index = 0;for (int i = 0; i < range; i++){while (count[i]--)//这里是为了把上面count对应次数给传进arr{arr[index++] = i + min;//表示arr数组的下标从0开始，存放数据}}
}

test.c

#include "Sort.h"int main()
{int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };int n = sizeof(a) / sizeof(int);printf("排序前：");PrintArr(a, n);CountSort(a, n);printf("排序后：");PrintArr(a, n);return 0;
}

计数排序的特性：

计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。 而且只能适用于整数排序，无法对小数排序。

时间复杂度：O(N + range)

空间复杂度：O(range)

稳定性：稳定

---

3.排序算法复杂度及稳定性分析

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

比如：6 2 4 9 1 2

排序后：1 2 2 4 6 9

一开始有两个2，一个在前面，一个在后面。

排序后也有两个2，一个在前面，一个在后面。

如果排序后前面的2还是在后面的2的前面，就称相对次序保持不变。称这种排序算法是稳定的；否则称为不稳定的。

稳定性验证案例

1. 直接选择排序：5 8 5 2 9

2. 希尔排序：5 8 2 5 9

3. 堆排序：2 2 2 2

4. 快速排序：5 3 3 4 3 8 9 10 11