C语言数据结构–排序算法
1.排序的概念及其运用
1.1排序的概念
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起 来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记 录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，
而在排序后的序列中，r[i]仍 在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
1.2 常见的排序算法
// 排序实现的接口
// 插入排序
void InsertSort(int* a, int n);
// 希尔排序
void ShellSort(int* a, int n);
// 选择排序
void SelectSort(int* a, int n);
// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);
// 冒泡排序
void BubbleSort(int* a, int n)
// 快速排序
void QuickSort(int* a, int left, int right);
// 归并排序
void MergeSort(int* a, int n)
// 测试排序的性能对比
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);
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];
}
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();
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);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
}
1. 插入排序
1.1基本思想：
直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐 个插入到一个已经排好序的有序序列中， 直到所有的记录插入完为止，得到一个新的有序序列 实际中我们玩扑克牌时，就用了插入排序的思想
1.2直接插入排序：
当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序， 此时用array[i]的排 序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入， 原来位置上的元素顺序后移直接插入排序的特性总 结：
// 插入排序
//时间复杂度O(N*N)
//空间复杂度O(1)
void InsertSort(int* a, int n)
{
assert(a);
//把end+1的数据插入到【0，end】的有序区间
for (int i = 0; i < n - 1; i++)
{
int end=i;
int tmp = a[end + 1];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
//无论是break出来的还是比end大的都要放到end后面的位置
a[end + 1] = tmp;
}
}
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定
### 1.3 希尔排序( 缩小增量排序 ) 希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有 记录分成个组， 所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。 当到达=1时，所有记录在统一组内排好序。
希尔排序的特性总结：
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。
当gap == 1时，数组已经接近有序的 了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，需要进行推导，推导出来平均时间复杂度： O(N^1.3— N^2） 4. 稳定性：不稳定
// 希尔排序(直接插入排序的优化)
//先预排序，后直接排序
//来平均时间复杂度： O(N^1.3—N ^ 2）
void ShellSort(int* a, int n)
{
//gap大于1相当于预排序。让数组接近有序
//gap==1，相当于直接插入排序，保证有序
int gap=n;
while (gap > 1)
{
gap = gap / 3 + 1;//+1保证最后一次一定是1
//多组并排
for (int i = 0; i < n - gap; ++i)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] >tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
2选择排序
2.1基本思想：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全 部待排序的数据元素排完 。
2.2 直接选择排序:
在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素
若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个） 元素交换
在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩 余1个元素
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
// 选择排序()
//时间复杂度: o(N*N);
void SelectSort(int* a, int n)
{
assert(a);
int begin = 0, end = n - 1;
while (begin <= end)
{
//[begin,end]之间找出最小的数和最大的数的下标
int mini, maxi;
mini = maxi = begin;
for (int i = begin+1; i <= end; ++i)
{
if (a[i]>a[maxi])
{
maxi = i;
}
if (a[i] < a[mini])
{
mini = i;
}
}
//交换
Swap(&a[begin], &a[mini]);
//*******如果max和begin位置重叠，则maxi的位置需要更正******
if (begin == maxi)
{
maxi = mini;
}
Swap(&a[end], &a[maxi]);
//缩小区间
++begin;
--end;
}
}
直接选择排序的特性总结：
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
## 2.3 堆排序
堆排序的特性总结：
// 堆排序
void AdjustDwon(int* a, int n, int root)
{
int parent = root;
int child = parent * 2 + 1;
while (child<n)
{
if (child + 1 < n && a[child + 1] > a[child])
{
++child;
}
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//时间复杂度是（N*log N）
void HeapSort(int* a, int n)
{
//排升序，建大堆
for (int i =( n - 1-1)/2;i>=0; --i)
{
AdjustDwon(a, n, i);
}
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDwon(a, end, 0);
--end;
}
}
1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
## 3. 交换排序 基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置， 交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移 动。
3.1冒泡排序
// 冒泡排序
//时间复杂度 O(N*N) 等差数列
void BubbleSort(int* a, int n)
{
int end = n;
while (end > 0)
{
int exchange = 0;
for (int i = 0; i < end ; ++i)
{
if (a[i - 1] > a[i])
{
Swap(&a[i - 1], &a[i]);
exchange = 1;
}
}
//如果一趟冒泡排序没有发生交换，则前部分已经有序，不需要交换
if (exchange == 0)
{
break;
}
}
}
冒泡排序的特性总结：
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定
3.2 快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为： 任取待排序 元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有 元素均小于基准值， 右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所 有元素都排列在相应位置上为止。
将区间按照基准值划分为左右两半部分的常见方式有：
整体实现思想：
快速排序的三种方法
//解决：三数取中法：
//
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//a[begin] > a[mid]
{
if (a[mid] > a[end])
{
return mid;
}
else if (a[begin] < a[end])
{
return begin;
}
else
{
return end;
}
}
}
//单趟排序
//1.左右指针法
int PartSort1(int* a, int begin, int end)
{
int midIndex = GetMidIndex(a, begin, end);
//三数选出来的放在右边，后面还是排序
Swap(&a[midIndex],&a[end]);
int keyindex = end;
while (begin < end)
{
//选最右边为key，一定要左边begin先走，这样保证他们相遇的位置是一个比key大的位置
// 同理，最左边为key的时候，选最右边先走
//begin找大
while (begin < end && a[begin] <= a[keyindex])
{
++begin;
}
//end找小
while (begin < end && a[end] >= a[keyindex])
{
--end;
}
Swap(&a[begin], &a[end]);
}
Swap(&a[begin], &a[keyindex]);
return begin;
}
//2.挖坑法
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];
}
a[begin] = key;
return begin;
}
//3.前后指针法
//cur找到比key小的就停下来，然后++prev，然后cur和prev的位置的值交换
int PartSort3(int* a, int begin, int end)
{
int midIndex = GetMidIndex(a, begin, end);
//三数选出来的放在右边，后面还是排序
Swap(&a[midIndex], &a[end]);
int prev = begin - 1;
int cur = begin;
int keyindex =end;
while (cur < end)
{
while(a[cur] < a[keyindex]&&++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
++cur;
}
Swap(&a[++prev],&a[cur]);
return prev;
}
// 快速排序
//[left right]闭区间
//时间复杂度 最后的情况O(N*log N----N*N)
//最坏的情况是选到最大或者最小的数
//空间复杂度:O（log N）
void QuickSort(int* a, int left, int right)
{
assert(a);
if (left >=right)
{
return;
}
//优化.
//小区间使用插入排序去排，减少整体的递归次数
if ((right-left)+1>10)
{
int div = PartSort3(a, left, right);
//[left div-1] div [div+1 right];
QuickSort(a, left, div - 1);
QuickSort(a, div + 1, right);
}
else
{
//如果小于十个数，则进行插入排序,不再递归
InsertSort(a + left, right - left + 1);
}
}
快速排序的特性总结：
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定
## 4.归并排序 基本思想：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法 （Divide and Conquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序 列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二 路归并。 归并排序核心步骤：
归并排序的特性总结：
//非递归--栈 后进先出
//非递归：1.提高效率（递归建立栈帧有消耗）
// 2.递归的最大缺陷是，如果栈帧的深度太深，可能导致栈溢出。，因为系统
// 空间一般不大在M级别；
// 数据结构栈模拟非递归，数据储存在堆上，堆是G级别的
void QuickSortNonR(int* a, int left, int right)
{
//栈模拟实现
ST st;
StackInit(&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 div = PartSort3(a, begin, end);
//[begin div-1] div [div+1, end]
if (div + 1 < end)
{
StackPush(&st, end);
StackPush(&st, div + 1);
}
if (begin < div - 1)
{
StackPush(&st, div-1);
StackPush(&st, begin);
}
}
StackDestory(&st);
}
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++];
//把归并好的再tmp的数据拷贝回原数组
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;
}
//[left mid] [mid+1,right] 都有序，则可以合并
int mid = (left + right) / 2;
//[left mid]
_MergeSort(a, left, mid , tmp);
// [mid+1,right]
_MergeSort(a, mid+1, right, tmp);
//归并[left mid] [mid+1,right]有序
MergeArr(a, left, mid,mid+1,right,tmp);
}
// 归并排序递归实现
//两端有序数合并，依旧有序
//时间复杂度 O(N*log N)
//空间复杂度 O(N)
void MergeSort(int* a, int n)
{
assert(a);
int* tmp=malloc(sizeof(int)*n);
_MergeSort(a, 0,n-1,tmp);
free(tmp);
}
// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
assert(a);
int* tmp = malloc(sizeof(int) * n);
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
//控制[i,i+gap-1] [i+gap,i+2*gap-1];
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, 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);
}
gap *= 2;
}
free(tmp);
}
1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问 题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
文件的归并排序–外磁盘排序
void _MergeFile(const char* file1, const char* file2, const char* mfile)
{
FILE* fout1 = fopen(file1, "r");
if (fout1 == NULL)
{
printf("打开文件夹失败\n");
exit(-1);
}
FILE* fout2 = fopen(file2, "r");
if (fout2 == NULL)
{
printf("打开文件夹失败\n");
exit(-1);
}
FILE* fin = fopen(mfile, "w");
if (fin == NULL)
{
printf("打开文件夹失败\n");
exit(-1);
}
int num1, num2;
int ret1=fscanf(fout1, "%d\n", &num1);
int ret2 = fscanf(fout2, "%d\n", &num2);
while (ret1!=EOF&&ret2!=EOF)
{
if (num1 < num2)
{
fprintf(fin, "%d\n", num1);
//读写文件的时候文件指针是自己动的
ret1 = fscanf(fout1, "%d\n", &num1);
}
else
{
fprintf(fin, "%d\n", num2);
ret2 = fscanf(fout2, "%d\n", &num2);
}
}
while (ret1!=EOF)
{
fprintf(fin, "%d\n", num1);
ret1 = fscanf(fout1, "%d\n", &num1);
}
while (ret2 != EOF)
{
fprintf(fin, "%d\n", num2);
ret2 = fscanf(fout2, "%d\n", &num2);
}
fclose(fout1);
fclose(fout2);
fclose(fin);
}
//文件中的数据排序
void MergeSortFile(const char* file)
{
FILE* fout = fopen(file, "r");
if (fout == NULL)
{
printf("打开文件夹失败\n");
exit(-1);
}
//分割成一段一段数据，内存排序后写到小文件里面
int n = 10;
int a[10];
int i = 0;
int filei = 1;
int num = 0;
char filename[20];
while (fscanf(fout,"%d\n", &num)!=EOF)
{
if (i < n-1)
{
a[i++] = num;
}
else
{
a[i] = num;
QuickSort(a, 0, n - 1);
sprintf(filename, "sub\\%d", filei++);
FILE*fin=fopen(filename, "w");
if (fin == NULL)
{
printf("打开文件夹失败\n");
exit(-1);
}
for(int i = 0; i < n; i++)
{
fprintf(fin,"%d\n", a[i]);
}
fclose(fin);
i = 0;
}
}
//========================文件归并=============================//
//利用互相合并到文件，实现整体有序
char mfile[100]="12";
char file1[100] = "sub\\1";
char file2[100];
for (int i = 2; i <=n; ++i)
{
sprintf(file2,"sub\\%d", i);
//sprintf(mfile, "sub\\%s%d.txt",mfile, i);
//读取file1，和file2进行归并出mfile
_MergeFile(file1, file2, mfile);
strcpy(file1, mfile);
sprintf(mfile, "%s%d", mfile,i+1);
}
fclose(fout);
}
非比较排序 计数排序
//非比较排序（基数排序和计数排序）
//1.计数排序 =======费空间 -----只使用于整型
// 如果是浮点数或者字符串还是比较排序
//时间复杂度 O(N+range) 空间复杂度O(range)
//统计出数组中每个数出现的次数
//遍历原数组，数组中每个值是多少就对统计次数的数组位置的值++
void CountSort(int* a,int n)
{
assert(a);
int min = a[0];
int max = a[0];
for (int i = 0; i < n; ++i)
{
if (a[i]>max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
int range = max - min+1;
int* countArr = (int*)malloc(sizeof(int) * range);
memset(countArr, 0, sizeof(int) * range);
//统计次数
for (int i = 0; i < n; ++i)
{
//减去最小的数，就是相对位置，节省空间
countArr[a[i]-min]++;
}
//排序
int index = 0;
for (int j = 0; j < range; ++j)
{
//有几个值就写几个值
while (countArr[j]--)
{
//相对位置
a[index++] = j + min;
}
}
free(countArr);
}
## 5.排序算法复杂度及稳定性分析
稳定性-----数组中相同的值，排完序相对顺序可以做到不变的就是稳定的，否则就不稳定
6.选择题练习
1. 快速排序算法是基于（ ）的一个排序算法。
A分治法
B贪心法
C递归法
D动态规划法
2.对记录（54,38,96,23,15,72,60,45,83）进行从小到大的直接插入排序时，当把第8个记录45 插入到有序表时，为找到插入位置需比较（ ）次？（采用从后往前比较）
A 3
B 4
C 5
D 6
3.以下排序方式中占用O（n）辅助存储空间的是
A 简单排序
B 快速排序
C 堆排序
D 归并排序
4.下列排序算法中稳定且时间复杂度为O(n2)的是（ ）
A 快速排序
B 冒泡排序
C 直接选择排序
D 归并排序
5.关于排序，下面说法不正确的是
A 快排时间复杂度为O(N*logN)，空间复杂度为O(logN)
B 归并排序是一种稳定的排序,堆排序和快排均不稳定
C 序列基本有序时，快排退化成冒泡排序，直接插入排序最快
D 归并排序空间复杂度为O(N), 堆排序空间复杂度的为O(logN)
6.下列排序法中，最坏情况下时间复杂度最小的是（ ）
A 堆排序
B 快速排序
C 希尔排序
D 冒泡排序
7.设一组初始记录关键字序列为(65,56,72,99,86,25,34,66)，则以第一个关键字65为基准而得到 的一趟快速排序结果是（）
A 34，56，25，65，86，99，72，66
B 25，34，56，65，99，86，72，66
C 34，56，25，65，66，99，86，72
D 34，56，25，65，99，86，72，66
答案： 1.A 2.C 3.D 4.B 5.D 6.A 7.A
7.LeetCode OJ题
排序数组：912. 排序数组 - 力扣（LeetCode） https://leetcode.cn/problems/sort-an-array/description/)试试哪个写排序可以跑过这个oj 测试
