数据结构之五：排序
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);
// 返回区间分割的keyIndex
int 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++];
else
tmp[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;*/
}五、内外排序
内（外）排序并不是特指某一种排序算法，而是针对不同存储的空间的排序方法。
内排序：指的是在内存中进行排序。
外排序：指的是在外存（文件、磁盘）中进行排序。