数据结构之五：排序

  void*类型的实现：排序（void*类型）-CSDN博客

一、插入排序

1、直接插入排序

思想：把待排序的数据逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

单趟：

整体： 

实现：

void InsertSort(int* arr, int sz) {assert(arr);int i = 0;for (i = 0; i < sz - 1; i++) {// 单趟：int end = i; // 有序序列的最后一个值int tmp = arr[end + 1];// 把end后面的第一个数据 往 0~end这个有序区间中插入while (end >= 0) {if (tmp < arr[end]) {arr[end + 1] = arr[end];end--;} else {break;}}arr[end + 1] = tmp;}
}

 2、希尔排序

希尔排序本质上是对直接插入排序的优化。

 代码实现：

void ShellSort(int* arr, int n) {// 1.gap>1相当于预排序,让数组接近有序// 2.gap==1相当于直接排序,保证有序int gap = n;int i = 0;while (gap > 1) {gap = gap / 3 + 1; // +1保证了最后一次gap一定是1// gap==1 最后一次就相当于直接插入排序// gap /= 2:效果没有/3好for (i = 0; i < n - gap; i++) {int end = i;int tmp = arr[end + gap];while (end >= 0) {if (tmp < arr[end]) {arr[end + gap] = arr[end];end -= gap;} else {break;}arr[end + gap] = tmp;}}}
}

对希尔排序多组并排的一个理解： 

•  希尔排序的时间复杂度在O(N^1.3~N^2)之间。
• 当且仅当待排数据有序的情况下希尔排序的时间复杂度劣于直接插入排序。

二、选择排序

 1、直接选择排序

思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。（每次选一个数放到，放到新的位置）。

直接选择排序是很基础的一个排序，实现：

// 选择排序
// 优化，一次选两个数（最大和最小）放在合适位置
void SelectSort(int* arr, int n) {assert(arr);int begin = 0;int end = n - 1;while (begin < end) {// 在begin和end之间找出最大的数和最小的数的下标int maxi = begin;int mini = begin;int i = 0;for (i = begin + 1; i <= end; i++) {if (arr[maxi] < arr[i]) {maxi = i;}if (arr[mini] > arr[i]) {mini = i;}}Swap(&arr[begin], &arr[mini]);// 如果maxi和begin重叠，则maxi的值需要修正。if (begin == maxi) {maxi = mini;}Swap(&arr[end], &arr[maxi]);begin++;end--;}
}

时间复杂度：

• T(N)=N*(N/2)=1/2*N^2，（优化后是N*N/2，优化前是N*N）。
• 即：O(N^2) 。

2、堆排序

思路：堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建小堆，排降序建大堆。

直接实现：（在堆中有过讲解）

// 向下调整算法
void AdjustDown(int* arr, int n, int root) {int parent = root;int child = 2 * parent + 1;while (child < n) {if (child + 1 < n && arr[child] < arr[child + 1]) {child++;}if (arr[parent] < arr[child]) {Swap(&arr[parent], &arr[child]);parent = child;child = parent * 2 + 1;} else {break;}}
}
void HeapSort(int* arr, int n) {// 排升序,建大堆int i = 0;for (i = (n - 1 - 1) / 2; i >= 0; i--) {AdjustDown(arr, n, i); // 把arr调整为大堆}for (i = n - 1; i >= 0; i--) {Swap(&arr[i], &arr[0]);AdjustDown(arr, i, 0); // 排序}
}

三、交换排序

基本思想：交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。

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

1、冒泡排序

实现：

void BubbleSort(int* arr, int n) {int end = n;while (end > 0) {int exchange = 0;// 一趟for (int i = 1; i < end; i++) {if (arr[i - 1] > arr[i]) {Swap(&arr[i - 1], &arr[i]);exchange = 1;}}//优化：// 如果一趟冒泡的过程中没有发生交换，则前部分已经有序，不需要在冒泡if (exchange == 0) {break;}end--;}
}

2、快速排序

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

a.递归

实现：

// 三数取中：找到不大不小的数，让排有序时变为最优
int GetMidIndex(int* a, int begin, int end) {int mid = (begin + end) / 2;if (a[begin] < a[mid]) {if (a[mid] < a[end]) {return mid;} else if (a[begin] > a[end]) {return begin;} else {return end;}} else {if (a[mid] > a[end]) {return mid;} else if (a[begin] < a[end]) {return begin;} else {return end;}}
}int PartSort1(int* a, int begin, int end){//单趟快排1： 左右指针法// 三数取中的优化int midIndex = GetMidIndex(a, begin, end);Swap(&a[midIndex], &a[end]);int key = a[end];int keyindex = end;// 如果是右边做key，那么一定让左边先走，这样保证它们相遇的位置会比key大while (begin < end) {while (begin < end && a[begin] <= key) {begin++;}while (begin < end && a[end] >= key) {end--;}Swap(&a[begin], &a[end]);}Swap(&a[begin], &a[keyindex]);return end;
}void QuickSort(int* a, int left, int right) {assert(a);if (left < right) {int div = PartSort(a, left, right);// PrintArray(a, right - left + 1);// printf("[%d,%d]%d[%d,%d]\n", left, div - 1, div, div + 1,right);//[left,div-1]QuickSort(a, left, div - 1);//[div+1,right]QuickSort(a, div + 1, right);}
}

---

 对于单趟快排的其他办法：

法2：挖坑法，直接覆盖数据（不在调用Swap函数，性能比左右指针快一点）。

// 挖坑法：
int PartSort2(int* a, int begin, int end) {// 三数取中的优化int midIndex = GetMidIndex(a, begin, end);Swap(&a[midIndex], &a[end]);int key = a[end];// 挖出一个坑，可以直接把数据填入到相应位置：对左右指针法的一点修改while (begin < end) {while (begin < end && a[begin] <= key) {begin++;}// 左边找到比key大的，填到右边的坑，begin的位置形成新的坑a[end] = a[begin];while (begin < end && a[end] >= key) {end--;}// 右边找到比key小的，填到左边的坑，end的位置形成新的坑a[begin] = a[end];}// 把key填入到begin和end相遇的位置上（最后一个坑）a[end] = key;return end;
}

法3：前后指针法

// 前后指针法
int PartSort3(int* a, int begin, int end) {int prev = begin - 1;int cur = begin;int key = a[end];int keyIndex = end;while (cur < end) {if (a[cur] < key && ++prev != cur) {Swap(&a[prev], &a[cur]);}cur++;}Swap(&a[++prev], &a[keyIndex]);return prev;
}

---

 b.小区间优化

小区间使用插入排序可以减少递归层数，提升快排的效率：（小区间优化）

当数据分割到小于等于10个数据时候，利用插入排序提升效率。

Q：为什么使用插入排序，而不是时间复杂度的更低的希尔排序或者堆排序？

A1：快速排序不断分割后，子序列趋近于有序。

        前文中讲过，当待排数据趋近有序时，直接插入排序的时间复杂度趋近于O(N)，因此，使用直接插入排序的性能要优于希尔排序和堆排序。

A2：希尔排序、堆排序、快速排序，都是对大量数据的排序。

        对于较少数据的排序（特别是趋近于有序的数据），使用插入排序的综合性能会更高一点。（插入排序对于小数据的排序性能不一定优于或者差于其他三种排序）。

void QuickSort(int* a, int left, int right) {assert(a);if (right - left + 1 < 10) {// 小区间使用插入排序InsertSort(a + left, right - left + 1);} else {// 大区间使用快速排序if (left < right) {int div = PartSort1(a, left, right);// PrintArray(a, right - left + 1);// printf("[%d,%d]%d[%d,%d]\n", left, div - 1, div, div + 1,right);//[left,div-1]QuickSort(a, left, div - 1);//[div+1,right]QuickSort(a, div + 1, right);}}
}

c.非递归（栈）

大区间单趟排，分割的两个小区间不在递归，而是保存在栈里面。

Q：为什么这里要用非递归实现呢？

A：递归实现的快排是由风险的，当待排的数据量特别大的时候，不断的递归会产生大量的栈帧，而计算机的栈帧仅有8M左右的大小，会发生栈溢出。

实现：

void QuickSortNoR(int* a, int left, int right) {// 栈模拟实现Stack st;StackInit(&st); // 一定要记得初始化StackPush(&st, right);StackPush(&st, left);while (!StackEmpty(&st)) {int begin = StackTop(&st);StackPop(&st);int end = StackTop(&st);StackPop(&st);// 返回区间分割的keyIndexint div = PartSort1(a, begin, end);// 先对左区间分割,栈中先入右区间if (div + 1 < end) {// 入右区间右值StackPush(&st, end);// 入右区间左值StackPush(&st, div + 1);}if (div - 1 >= begin) {// 入左区间右值StackPush(&st, div - 1);// 入左区间左值StackPush(&st, begin);}}StackDestory(&st);
}//非递归同样可以使用小区间优化

---

 快排的时间复杂度分析： 

快排的时间复杂度：O(N*logN)。

快排的空间复杂度：O(logN)。（即栈帧的深度）

---

四、归并排序

基本思想：归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。（不断地拆分，让子序列有序，归并一个序列时，保持有序）。

二路归并：将两个有序表合并成一个有序表。

分解:（递归图）

 归并:

 递归实现

时间复杂度是：O(N*logN)

空间复杂度是：O(N) 

// 归并函数
void MergeArr(int* a, int begin1, int end1, int begin2, int end2, int* tmp) {int left = begin1, right = end2;int index = begin1;while (begin1 <= end1 && begin2 <= end2) {if (a[begin1] < a[begin2])tmp[index++] = a[begin1++];elsetmp[index++] = a[begin2++];}while (begin1 <= end1)tmp[index++] = a[begin1++];while (begin2 <= end2)tmp[index++] = a[begin2++];for (int i = left; i <= right; i++)a[i] = tmp[i];
}
// 归并的子函数
void _MergeSort(int* a, int left, int right, int* tmp) {if (left >= right)return;int mid = (left + right) / 2;//[left,mid] [mid+1,right]// 有序则可以合并,现在他们没有序,子问题解决_MergeSort(a, left, mid, tmp);_MergeSort(a, mid + 1, right, tmp);// 归并[left,mid] [mid+1,right]MergeArr(a, left, mid, mid + 1, right, tmp);
}// 递归实现归并排序
void MergeSort(int* a, int n) {assert(a);int* tmp = (int*)malloc(sizeof(int) * n);_MergeSort(a, 0, n - 1, tmp);free(tmp);
}

非递归实现

非递归需要修正边界

非递归的时间复杂度：（从while循环入手）O(N*logN)

非递归的空间复杂度：O(N)

void MergeSortNoR(int* a, int n) {assert(a);int* tmp = (int*)malloc(sizeof(int) * n);// 迭代实现int gap = 1;int i = 0;while (gap < n) {for (i = 0; i < n; i += 2 * gap) {//[i,i+gap-1] [i+gap,i+2*gap-1]int begin1 = i;int end1 = i + gap - 1;int begin2 = i + gap;int end2 = i + 2 * gap - 1;// 1、合并时只有第一组，第二组不存在就不需要合并if (begin2 >= n) {break;}// 2、合并时第二组只有部分数据，需要修正end2边界if (end2 >= n) {end2 = n - 1;}MergeArr(a, begin1, end1, begin2, end2, tmp);PrintArray(a, n);}gap *= 2;}/*free(tmp);tmp == NULL;*/
}

五、内外排序

内（外）排序并不是特指某一种排序算法，而是针对不同存储的空间的排序方法。

内排序：指的是在内存中进行排序。

外排序：指的是在外存（文件、磁盘）中进行排序。

外排序实现需要利用C对文件的操作：

//合并两个有序数据的文件
void _MergeFile(const char* file1, const char* file2, const char* mFile) {FILE* pf1 = fopen(file1, "r");if (pf1 == NULL) {printf("2:%s\n", strerror(errno));exit(-1);}FILE* pf2 = fopen(file2, "r");if (pf2 == NULL) {printf("3:%s\n", strerror(errno));exit(-1);}FILE* fin = fopen(mFile, "w");if (fin == NULL) {printf("4:%s\n", strerror(errno));exit(-1);}int num1 = 0;int num2 = 0;int ret1 = fscanf(pf1, "%d\n", &num1) != EOF;int ret2 = fscanf(pf2, "%d\n", &num2) != EOF;while (ret1 != EOF && ret2 != EOF) { // 文件指针是自动的，都往后移动if (num1 < num2) {fprintf(fin, "%d\n", num1);ret1 = fscanf(pf1, "%d\n", &num1);// fseek(pf2, SEEK_CUR, -1);} else {fprintf(fin, "%d\n", num2);ret2 = fscanf(pf2, "%d\n", &num2);// fseek(pf1, SEEK_CUR, -1);}}while (ret1 != EOF) {fprintf(fin, "%d\n", num1);ret1 = fscanf(pf1, "%d\n", &num1);}while (ret2 != EOF) {fprintf(fin, "%d\n", num2);ret2 = fscanf(pf2, "%d\n", &num2);}fclose(pf1);fclose(pf2);fclose(fin);
}void MergeSortFile(const char* file) {FILE* pf = fopen(file, "r");if (pf == NULL) {printf("1:%s\n", strerror(errno));exit(-1);}// 分割成小文件,内存排序后写到小文件中int n = 10;int a[10] = {0};int num = 0;int i = 0;// char* subfile = (char *)malloc(sizeof(char));char subfile[20];int filei = 0;while (fscanf(pf, "%d\n", &num) != EOF) {if (i < n - 1) {a[i++] = num;} else {a[i] = num;QuickSort(a, 0, n - 1);sprintf(subfile, "%d", filei++);FILE* fin = fopen(subfile, "w");for (i = 0; i < n; i++) {fprintf(fin, "%d\n", a[i]);}fclose(fin);i = 0;memset(a, 0, sizeof(int) * n);}}// 文件两两合并char mFile[100] = "12";char file1[100] = "1";char file2[100];for (i = 1; i <= n; i++) {sprintf(file2, "%d", i);// 读取file1和file2，归并出mfile_MergeFile(file1, file2, mFile);strcpy(file1, mFile);sprintf(mFile, "%s%d", mFile, i + 1);}fclose(pf);
}

六、非比较排序

        非比较排序是很“小众”的排序，因为这两种排序只适用于整数类型的排序。不能排序浮点数和字符串型的数据，对于这些类型的数据要用比较排序法来排序。

1、计数排序

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。是一种非比较排序。

1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中

实现：

void CountSort(int* a, int n) {int min = a[0];int max = a[0];int i = 0;for (i = 0; i < n; i++) {if (min > a[i]) {min = a[i];}if (max < a[i]) {max = a[i];}}int range = max - min + 1;int* countArr = (int*)calloc(range, sizeof(int));if (countArr == NULL) {return;}// memset(countArr, 0, sizeof(int) * range);for (i = 0; i < n; i++) {countArr[a[i] - min]++; // 偏移量映射}int index = 0;for (i = 0; i < range; i++) {int j = 0;for (j = 0; j < countArr[i]; j++) {a[index++] = i + min;}}free(countArr);
}

2、基数排序

        基数排序即：桶排序。可以参考：【算法】桶排序（Bucket Sort）详解-CSDN博客，桶排序不是很重要，了解即可。

---

总结

1、几种排序的时间复杂度比较

2、排序的稳定性

          稳定性：由某一算法完成的排序后，数组中相同元素的相对位置保持不变。即表示该算法是稳定的，否则表示该算法不稳定。

3、归并外部文件的排序（了解即可）