目录
一 . 排序概念及运用
1.1 排序的概念
1.2 排序的应用
1.3 常见的排序算法
二 . 插入排序
2.1 直接插入排序
2.1 复杂度分析
2.3 希尔排序
2.4 希尔排序时间复杂度分析
三 . 选择排序
3.1 直接选择排序
3.2 堆排序
一 . 排序概念及运用
1.1 排序的概念
排序 : 所谓排序 ， 就是使一条记录 ， 按照其中的某个或某些关键字的大小，递增 或 递减的排序起来的操作 。
1.2 排序的应用
排序在生活中无处不在 ， 如果没有排序 ， 那么许多业务也不会实现
1 . 院校排名
2 . 购物筛选排序
1.3 常见的排序算法
二 . 插入排序
基本思想 :
直接插入排序是一种简单的插入排序算法 ， 其基本思想是 : 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中 ， 直到所有记录插入完为止 ， 得到一个新的有序序列 。
在实际生活中 ， 玩扑克牌就使用了 插入排序 的思想 !
2.1 直接插入排序
插入排序是在已经有序序列中 ， 插入新的数据 ， 形成一个新的有序序列
直接插入排序 ， 需要一个变量来存储需要插入的数据(tmp) , 另一个变量初始为有序序列的最后一个位置 (end)， arr[end] 与 tmp 比较 ， 谁大谁往后排 。
这里我们依旧创建三个文件 ， 方便文件的管理 ， 使用一个test.c 文件也是可以实现的。
test.c
#include "Sort.h"
void PrintArr(int* arr,int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
void test()
{
int a[] = { 5,3,9,6,2,4,7,1,8 };
int n = sizeof(a) / sizeof(a[0]);
printf("排序之前:");
PrintArr(a, n);
InsertSort(a, n);
printf("排序之后:");
PrintArr(a, n);
}
int main()
{
test();
return 0;
}Sort.c
#include "Sort.h"
//直接插入排序
void InsertSort(int* arr, int n)
{
for (int i = 0; i < n-1; i++)
{
int end = i;
int tmp = arr[end + 1];
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + 1] = arr[end];
end--;
}
else
{
break;
}
}
arr[end + 1] = tmp;
}
}Sort.h
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
//直接插入排序
void InsertSort(int* arr, int n);
2.1 复杂度分析
直接插入排序的特性总结 :
1 . 元素集合越接近有序 ， 直接插入排序算法时间的效率越高
2 . 时间复杂度 : O ( n^2)
3 . 空间复杂度 : O （1）
对比之前学过的 冒泡排序 ， 堆排序 堆排序和TOP-K问题-CSDN博客
1 . 冒泡排序时间复杂度为 O(n^2)
2 . 堆排序时间复杂度为 O (n * log n)
3 . 直接插入排序时间复杂度为 O（n^2)
在冒泡排序中 ， 如果序列本身为有序 ， 时间复杂度最优 O(n) ； 在直接插入排序中 ， 如果序列为有序 ， 且为降序 ， 时间复杂度最差 O (n^2) , 但这种情况的出现概率很小 ，在一定程度上可以说 ， 直接插入排序的时间复杂度达不到 O(n^2) , 但也没比冒泡排序好了多少 。
以下测试以下三个方法运行时所需的时间 ， 单位为毫秒
从上面的测试结果我们可以得出 ， 堆排序的算法 时间复杂度相较于 冒泡排序 和 直接插入排序的更优一些
test.c
#include "Sort.h"
#include <time.h>
#include <stdlib.h>
void PrintArr(int* arr,int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
void test()
{
int a[] = { 5,3,9,6,2,4,7,1,8 };
int n = sizeof(a) / sizeof(a[0]);
printf("排序之前:");
PrintArr(a, n);
//InsertSort(a, n);
//BubbleSort(a, n);
HeapSort(a, n);
printf("排序之后:");
PrintArr(a, 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);
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);
}
int main()
{
//test();
TestOP();
return 0;
}Sort.c
#include "Sort.h"
//直接插入排序
void InsertSort(int* arr, int n)
{
for (int i = 0; i < n-1; i++)
{
int end = i;
int tmp = arr[end + 1];
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + 1] = arr[end];
end--;
}
else
{
break;
}
}
arr[end + 1] = tmp;
}
}
void Swap(int* x,int*y )
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//冒泡排序
void BubbleSort(int* arr, int size)
{
for (int i = 0; i < size - 1; i++)
{
int exchange = 0;
for (int j = 0; j < size - 1 - i; j++)
{
if (arr[j] > arr[j + 1]) {
exchange = 1;
Swap(&arr[j], &arr[j + 1]);
}
}
if (exchange == 0)
{
break;
}
}
}
//向下调整
void AdjustDown(int* arr, int parent, int n)
{
int child = parent * 2 + 1;
while (child < n)
{
//先找最小孩子
if (child + 1 < n && arr[child] < arr[child + 1])
{
child++;
}
if (arr[child] > arr[parent])
{
Swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else {
break;
}
}
}
//堆排序
void HeapSort(int* arr, int n)
{
//向下调整算法建堆
for (int i = n - 1 - 1; i >= 0; i--)
{
AdjustDown(arr, i, n);
}
int end = n - 1;
while (end > 0)
{
Swap(&arr[end], &arr[0]);
AdjustDown(arr, 0, end);
end--;
}
}
Sort.h
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
//直接插入排序
void InsertSort(int* arr, int n);
//冒泡排序
void BubbleSort(int* arr, int size);
//堆排序
void HeapSort(int* arr, int n);
2.3 希尔排序
在数组为降序时 ， 直接插入排序的时间复杂度为 O（n^2) , 那么可以优化吗 ？
-------> 可以 ， 将数组划分成多组来进行直接插入排序，降低时间复杂度
希尔排序法又称缩小增量法 。
希尔排序法的基本思想是 : 选定一个整数 ( 通常是gap = n/3 + 1 ) , 把待排序文件所有记录分成各组 ， 所有的距离相等的记录分在同一组内 ， 并对每一组内的记录进行排序 ，
然后gap = gap / 3 +1 得到下一个整数 ， 再将数组分成各组 ， 进行插入排序 ， 当 gap = 1 时 ， 就相当于直接插入排序 。
它是在直接插入排序算法的基础上进行改进而来的 ， 综合来说它的效率肯定是要高于直接插入排序算法的 。
思考 :
1 ) 为什么要分组 ？
通过分组来降低元素之间的比较次数，优化时间复杂度
2 ) 怎么分组 ?
通过间隔 gap (gap / 3 + 1 ) 的元素 组成一组
3 ）为什么要 +1 , 不直接 gap/3 ?
假设gap = 3 , gap/3 = 0 , 此时数据还没有排序好 就终止了排序 , 希望是当gap == 1 时 ， 预排序结束 ， 然后进行直接插入排序 。
4 ) 可以gap/2 , gap/8 吗？
可以 ， 视情况而论 ， 一般是 gap/3 , 因为除小了 ， 分组过多就过多 ； 除大了 ， 比较次数就多了
//希尔排序
void ShellSort(int* arr, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int i = 0; i < n - gap ; i++)
{
int end = i;
int tmp = arr[end + gap];
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + gap] = arr[end];
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = tmp;
}
}
}2.4 希尔排序时间复杂度分析
希尔排序时间复杂度不好计算。因为 gap 的取值很多 ，导致很难去计算 ， 因此很多书中给出的希尔排序的时间复杂度后不固定 。 《数据结构 （C语言版）》 -- 严蔚敏书中给出的时间复杂度为
这里我们大致记住 ， 希尔排序的时间复杂度比直接插入排序更优 ，并且大致上为 O（n^1.3) ， 下面是大致对希尔排序的时间复杂度进行估算 :
外层循环 : ： O() 或者 O(
) ，即 O(log n)
内层循环 :
通过以上分析 ， 可以画得如下曲线图 :
因此 ， 希尔排序在最初和最后的排序的次数都为 n ， 即前一阶段排序次数是逐渐上升的状态 ， 当达到某顶点时 ， 排序次数逐渐下降至 n , 而该顶点的计算暂时无法给出具体的计算过程 。
单位为毫秒 ， 通过性能的测试 ， 我们发现 ， 希尔排序的运行速度 很近似于 堆排序 ， 相较于直接插入排序 是一个 较优的算法 ！
三 . 选择排序
选择排序的基本思想 :
每一次从待排序的数据元素中选出最小（或最大）的一个元素 ， 存放在序列的起始位置 ，直到全部待排序的数据元素排完 。
3.1 直接选择排序
//直接选择排序
void SelectSort(int* arr, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int mini = begin, maxi = begin;
//找最大最小
for (int i = begin + 1; i <= end; i++)
{
if (arr[i] < arr[mini])
{
mini = i;
}
if (arr[i] > arr[maxi])
{
maxi = i;
}
}
//如果maxi == began
if (maxi == begin)
{
maxi = mini;
}
Swap(&arr[mini], &arr[begin]);
Swap(&arr[maxi], &arr[end]);
begin++;
end--;
}
}直接选择排序的思路比较好理解，但是 效率不是很高 ， 实际中 很少使用
1 ） 时间复杂度 : O( n ^ 2 )
2 ) 空间复杂度 : O ( 1 )
3.2 堆排序
堆排序(HeapSort) 是利用堆 这种数据结构所设计的一种排序算法 ， 他是选择排序的一种 。 它是通过堆来进行选择数据 。 需要注意的是 排升序要建大堆 ， 排降序建小堆 。
之前的文章详细介绍了堆排序 ， 这里不再赘述
堆排序和TOP-K问题-CSDN博客
