1.排序算法的概念及其运用
1.1 排序的概念
* 排序: 所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列 起来的操作。
* 稳定性: 假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这 些记 录的相对次 序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列 中，r[i]仍在r[j]之前，则称这种排 序算法是稳定的；否则称为不稳定的。
* 时间复杂度:排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
* 空间复杂度:是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
* 内部排序:是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
* 外部排序:数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
1.2 排序运用
像淘宝商品价格排序,各个学校的综合评分排名等，都运用了排序算法相关的知识.
1.3 常见的排序算法
2.常见排序算法的实现
2.1 插入排序
基本思想
直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一 个已经排好序的有序序列中，直到所有
void InsertSort(int* a, int n) { //n:待排序数字的个数;n=sizeof(a)/sizeof(int); assert(a);//函数断言 for (int i = 0; i < n - 1; ++i) { // 将x插入[0, end]有序区间 int end = i; int x = a[end+1]; while (end >= 0) { if (a[end] > x) { a[end + 1] = a[end]; --end; } else { break; } } a[end + 1] = x; } }
的记录插入完为止，得到一个新的有序 序 列实际中我们玩扑克牌时，就用了插入排序的思想.
2.1.1 直接插入排序
* 从第一个元素开始,该元素可以认为已经被排序;
* 取出下一个元素，在已经排序的元素序列中从后向前扫描；
* 如果该元素（已排序）大于新元素，将该元素移到下一位置；
* 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
* 将新元素插入到该位置后；
* 重复步骤2~5。
动图演示:
代码实现:
void InsertSort(int* a, int n) { //n:待排序数字的个数;n=sizeof(a)/sizeof(int); assert(a);//函数断言 for (int i = 0; i < n - 1; ++i) { // 将x插入[0, end]有序区间 int end = i; int x = a[end+1]; while (end >= 0) { if (a[end] > x) { a[end + 1] = a[end]; --end; } else { break; } } a[end + 1] = x; } }
直接插入排序特性总结:
1.元素集合越接近有序，直接插入排序算法的时间效率越高;
2. 时间复杂度：O(N^2) ;
3. 空间复杂度：O(1)，它是一种稳定的排序算法 ;
4. 稳定性：稳定;
2.1.2 希尔排序(缩小增量排序）
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所 有记录分成个 组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后 取, 重复上述分组和排序的工 作。当到达=1时，所有记录在统一组内排好序。
动图演示:
代码实现:
void ShellSort(int* a, int n) { //n:待排序数字的个数;n=sizeof(a)/sizeof(int); // 多次预排序(gap > 1) +直接插入 (gap == 1) int gap = n; while (gap > 1) { //gap = gap / 2; gap = gap / 3 + 1; // 多组并排 for (int i = 0; i < n - gap; ++i) { int end = i; int x = a[end + gap]; while (end >= 0) { if (a[end] > x) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = x; } } }
希尔排序的特性总结:
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的 了，这样就 会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对 比。
3. 希尔排序的时间复杂度不好计算，需要进行推导，推导出来平均时间复杂度： O(N^1.3— N^2）
4. 稳定性：不稳定
2.2 选择排序
基本思想:
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置， 直到 全部待排序的数据元素排完
2.2.1 直接选择排序
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：
* 初始状态：无序区为R[1..n]，有序区为空；
* 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当 前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和 R[i+1..n) 分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
* n-1趟结束，数组有序化了。
动图演示:
代码实现:
void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } void selectsort(int* a, int n) { assert(a); for (int i = 0; i < n - 1; i++) { int min = i; for (int j = i + 1; j < n; j++) { if (a[j] < a[min]) min = j; } swap(&a[min], &a[i]); } }
直接选择排序的特征总结:
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
2.2.2 堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
动图演示:
代码演示:
void Adjustdown(int* a,int n,int parent) { 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; } } } void heapsort(int* a, int n) { assert(a); for (int i = (n - 1 - 1) / 2; i >= 0; i--) { Adjustdown(a, n, i); } int end = n - 1; while (end >= 0) { swap(&a[end], &a[0]); Adjustdown(a, end, 0); end--; } }
堆排序的特征总结:
1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
