概述
排序是计算机程序设计中的一种重要操作，简单的说，可以使任意序列重新排列成一个按关键字有序的序列。
- 好处：
- 有序顺序可以采用查找效率较高的折半查找法
- 有如建造数表（无论是二叉树还是B-树）的过程本身就是一个排序的过程
稳定与否
- 若两个相等数，在排序前与排序后的顺序相同，则是稳定的排序，否则是不稳定的。
-
eg：
假设: a = b 稳定: a, b --> a, b 不稳定: a, b --> b, a
内（/外）部排序
- 内部排序：指的是带排序的记录存放在计算机存储器中进行的排序过程
- 插入排序
- 交换排序
- 选择排序
- 归并排序
- 计数排序
- 外部排序：指的是带排序的记录数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。
两种基本操作
- 比较两个关键字的大小
- 将记录从一个位置移动至另外一个记录
排序算法
- 下面正式介绍各种排序算法
- 都是从小到大排序
- 以整形为例
插入排序
- 直接插入排序，是一种最简单的排序方法
-
基本操作是将一个记录插入到已排好的有序表中从而得到一个新的、记录数增1的有序表。
void insertSort(int test[], int len) { if (len < 2) return; for (int i = 1; i < len; i++) { int tmp = test[i], j; for (j = i; j > 0 && tmp < test[j-1]; j--) { //把比插入元素大的元素后移 test[j] = test[j-1]; } //找打合适位置插入 test[j] = tmp; } }
希尔排序
- 插入排序改进版
- 改进：
- 通过比较相距一定间隔的元素来工作；
- 随着每一趟比较所用的距离随着算法的进行而减小；
- 直到只比较相邻元素的最后一趟排序位置。
-
为此，希尔排序有时也叫缩减增量排序。
void shellSort(int test[], int len) { for (int gap = len/2; gap > 0; gap /= 2) { //选取步长 for (int i = gap; i < len; i++) { //以步长进行的选择排序 int tmp = test[i], j; for (j = i; j >= gap && tmp < test[j-gap]; j -= gap) { test[j] = test[j-gap]; } //找到合适位置插入 test[j] = tmp; } } }
冒泡排序
- 每一轮都把这轮的最大放到最后的位置
- 如：
- 第一轮把最大的数字放到最后一位
- 第二轮把最大的数字放到倒数第二位
- 第三轮把最大的数字放到倒数第三位
- 以此类推
void bubbleSort(int test[], int len) { for (int i = 1; i < len; i++) { //每一轮都把这轮最大的数放到（‘len-i’位置） for (int j = 0; j < len-i; j++) { if (test[j] > test[j+1]) { int tmp = test[j+1]; test[j+1] = test[j]; test[j] = tmp; } } } }
选择排序
- 类似冒泡排序
- 但是交换次数减少，因为冒泡排序是通过每一次交换把数字替换，而选择排序是选出最小一位再交换，效果更好
- 找到每一轮的最小元素，然后替换，直到最后排序完成
- 如：
- 第一轮把最小的数字放到第一位
- 第二轮把最小的数字放到第二位
- 第三轮把最小的数字放到第三位
- 以此类推。
void selectSort(int test[], int len) { for (int i = 0; i < len; ++i) { //记录当前为最小元素 int index = i; //找到最小元素 for (int j = i+1; j < len; ++j) { if (test[j] < test[index]) { index = j; } } //如果找到的最小元素比记录的最小元素要小，那么替换当前最小元素 if (index != i) { int tmp = test[index]; test[index] = test[i]; test[i] = tmp; } } }