一.排序算法总结
1.各类排序算法总表
?2.排序算法的分类
- 按数据存储介质：内部排序和外部排序
- 按比较器个数：? ?串行排序和并行排序
- 按主要操作：? ? ? ?比较排序和基数排序
- 按辅助空间：? ?????原地排序和非原地排序
- 按稳定性：? ? ? ? ? ?稳定排序和非稳定排序
- 按自然性：???????????自然排序和非自然排序
?3.排序依据原则
- 插入排序：直接插入排序、折半插入排序、希尔排序
- 交换排序：简单选择排序、快速排序
- 选择排序：简单选择排序、堆排序
- 归并排序：2-路归并排序
- 基数排序
二.排序算法思想叙述与实现
?1.插入排序
- 直接插入排序
? ? ? ? 直接插入排序，是一种串行的比较排序算法，常用的思路是在数组a[n] 的第一个元素作为“哨兵”的形式，通过比较大小从而确定位置进行排序。
基本思路：1.将待排序的元素存入到哨兵位置（从第二个位置起）；2.通过与非哨兵的其他位置进行顺序比较确定排序位置；3.将此位置放到待排序的位置，将哨兵插入到此位置。结合下图进行理解。
?代码实现：
//直接插入排序
void InsertSort(int num[],int len)
{
int i, j;
for (i = 2; i < len; i++)
{
if (num[i] < num[i - 1]) { //若"<"，需将num[i]插入有序子表
num[0] = num[i]; //复制为哨兵
for (j = i - 1; num[0] < num[j]; --j) {
num[j + 1] = num[j]; //记录后移
}
num[j + 1] = num[0]; //插入到正确的位置
}
}
}总结：
- 折半插入排序
? ? ? ? 折半插入算法，对直接插入算法的一种改进，将查找正确位置的时候，通过折半查找的方法进行，从而减少查找的时间，提高算法的插入效率。
算法思路：1.将待排序的元素存入到哨兵位置（从第二个位置起）；2.通过折半查找的方法进行确定放置的位置；3.将此位置放到待排序的位置，将哨兵插入到此位置。
算法实现：
void BinsertSort(int num[], int len)
{
int i, j,low,high,mid;
for (i = 2; i < len; ++i) { //依次插入第2~第n个位置元素
num[0] = num[i]; //当前插入元素存入到“哨兵”位置
low = 1;
high = i - 1; //采用二分查找法查找插入位置
while (low <= high) {
mid = (low + high) / 2;
if (num[0] < num[mid])
high = mid - 1;
else low = mid + 1;
}
for (j = i - 1; j >= high + 1; --j)
num[j + 1] = num[j]; //移动元素
num[high + 1] = num[0]; //插入正确位置
}
}?总结：
- 希尔排序
? ? ? ? 希尔排序，是一种不稳定的排序算法，通过特定的函数来确定位置，从而插入到序列中。
算法思路：1.将待排序的序列分割成若干子序列；2.分别进行直接插入排序；3.全体记录进行一次全部插入排序。结合下图进行理解。
代码实现
//希尔排序
void ShellSort(int num[], int dlta[], int t,int len)
{
//按增量序列dlta[0……t-1]对数组num作希尔排序。
for (int k = 0; k < t; ++k) {
ShellInsert(num, dlta[k],len); //一趟增量为dlta[k]的插入排序
}
}
void ShellInsert(int num[], int dk,int len)
{
int i,j;
for (i = dk + 1; i <= len; ++i) {
if (num[i] < num[i - dk]) {
num[0] = num[i];
for (j = i - dk; j > 0 && (num[0] < num[j]); j = j - dk ){
num[j + dk] = num[j];
}
num[j + dk] = num[0];
}
}
}总结：
?
2.交换排序
- 冒泡排序
? ? ? ? 冒泡排序，最常见的排序算法之一，通过想煮水时冒泡那样子，从下面小到最上面大（反之亦然），通过不断的元素交换位置从而来确定最后的位置，每一趟必有一个元素确定位置。
算法思路：1.确定元素排序顺序；2.通过一个一个比较交换找到最大的放最后，再进行下一轮比较；3.排序n个元素传统算法需要n-1趟遍历交换。下面的代码实现是，添加了一个标志位，如果往后的元素都是顺序了，就不用再进行后面趟次的交换了。
代码实现：
//冒泡排序
void BubbleSort(int num[],int len) {
int m, j, flag = 1,x; //flag作为是否有交换的标记
for (m = 1; m <= len - 1 && flag == 1; m++) {
flag = 0;
for (j = 1; j <= m; j++) {
if (num[j] > num[j + 1]) { //发生逆序
flag = 1; //发生交换，flag置为1，若本趟没有发生交换，flag保持为0
x = num[j];
num[j] = num[j + 1];
num[j + 1] = x;
}
}
}
}总结：
- 快速排序
? ? ? ? 快速排序，快速排序通过选择一个中枢元素，然后数组进行分组，将大的放后，小的放前，然后再对大小两个组再进行同样的操作，运用递归的思想将数组不断地进行分组有序排序。
算法思路：1.任取一个元素（如：第一个）为中心pivot；2.使用两个指针，low?一个指向最前面的元素，high?一个指向最后面的元素，对low值与pivot进行比较，若是小则往后移动，若是大于，则对high值跟pivot进行比较，若是大于则往前移动，若是小于则与low值进行交换，再重复这一操作，直到low = high则停止；3.进行递归分组，直到low = high；
代码实现：
//快速排序
void QSort(int num[], int low, int high) {
if (low < high) {
int pivotloc = Partition(num, low, high);
//将num[low……high]一分为二，pivotloc为枢轴元素排好序的位置
QSort(num, low, pivotloc - 1); //对低子表递归排序
QSort(num, pivotloc + 1, high);//对高子表递归排序
}
}
int Partition(int num[], int low, int high) {
num[0] = num[low];
int pivot = num[low];
while (low < high) {
while (low < high && num[high] >= pivot) --high;
num[low] = num[high];
while (low < high && num[low] <= pivot) ++low;
num[high] = num[low];
}
num[low] = num[0];
return low;
}?总结：
3.选择排序
- 简单选择排序
? ? ? ? 简单选择排序，近似于打擂台的方法，设置一个元素默认为最小或最大，通过将其他元素跟其进行比较，从而选择到比它小的进行交换，有多少元素就进行多少趟的比对选择。
算法思路：1.选定一个元素为擂主；2.对其他元素通过与其进行比较从而选择元素进行交换位置；3.多趟进行交换。
代码实现：
//简单选择排序
void SelectSort(int num[],int len) {
int i, j,k;
for (i = 1; i < len; ++i) {
k = i;
num[0] = num[i];
for (j = i + 1; j < len; j++) {
if (num[j] < num[k]) k = j; //记录最小值位置
}
if (k != i) num[i] = num[k]; //交换
}
}总结：
- 堆排序
? ? ? ? 堆排序，是先进行堆建立，然后将元素通过堆的定义插入到堆中，并对堆不断调整后，成为一个大根堆或者小根堆。
算法思路：1.建立堆，将元素放置堆顶，然后再放入第二个元素，若是比它小则接入到孩子结点，若比它大则它成为顶点，顶点成为孩子结点。不断重复从而建立堆。2.堆排序，输出堆顶元素，在将叶子结点放到堆顶，再对堆顶元素跟其底下结点进行比较换位，从而是的每次输出的堆顶元素都为最大的。
代码实现：
//堆排序
void HeapAdjust(int num[], int s, int m)
{
//已知num[s……m]中记录的关键字除num[s]之外均满足堆的定义，
//本函数调整num[s]的关键字，使得num[s……m]成为一个大根堆
int j;
int rc = num[s];
for (j = 2 * s; j <= m; j *= 2) { //沿较大的孩子结点向下筛选
if (j < m && num[j] < num[j + 1]) ++j; //j为较大的记录的下标
if (rc >= num[j]) break;
num[s] = num[j]; //rc应插在位置s上
s = j;
}
num[s] = rc; //插入
}
void HeapSort(int num[],int n) { //n为数组长度，也为堆的个数
int i;
for (i = n / 2; i >= 1; i--)
HeapAdjust(num, i, n); //建初始堆
for (i = n; i > 1; i--) { //进行n-1趟排序
Swap(num[1], num[i]); //交换根与最后一个元素
HeapAdjust(num, 1, i - 1); //对num[1]到num[i-1]重新建堆
}
}?总结：
?
4.归并排序
? ? ? ? ?归并排序是对几个数组进行归并，通过数组中的排序，再进行数组与数组间的排序，从而将数组归并排序成一个数组。用以下图理解即可。代码需要具体问题具体分析。?
5.基数排序
? ? ? ? 基数排序，最主要的思想是进行分配+收集。其算法思想是设置若干个箱子，将关键字为k的记录放入第k个箱子，然后按序号将非空的连接。结合如下图理解即可。
?
?
?三.算法对比和总结
