常见八大排序算法

写于大二上期末数据结构考试前，做一个排序算法的总结。也是严蔚敏那版本教材上代码具体的编译实现。

1.简单选择排序

。一句话说，就是每次遍历挑选遍历最小的那个数填入相应的位置。并互换位置。
~~ 改进的一种思路是每次不仅选最小的往前放，也挑最大的往后放。这样只需遍历一半的次数就可以完成排序。简单排序代码过程简单，就不写注释了。

#include<iostream>
using namespace std;
void print(int a[], int n) {  for (int i = 0; i <= n; i++) {cout << a[i] << " ";}cout << endl;
}void selectSort(int a[], int n) {int min,temp;for (int i = 0; i <= n-1; i++) {min = i;for (int j = i + 1; j <= n; j++) {if (a[j] < a[min])min = j;}if(i!=min){temp = a[i];a[i] = a[min];a[min] = temp;}print(a, n);}
}
int main() {int a[8] = { 42,38,65,97,76,13,27,49 };cout << "初始序列如下" << endl;print(a, 7);cout << "下面输出每趟排序后的序列" << endl;selectSort(a,7);
//	print(a, 7);return 0;
}

2.直接插入排序

~~思路：首先将第一个元素看成有序表，第二个元素开始往后遍历时，在这个有序表找到插入的位置，比他大的元素后移，然后存放进去实现排序。

代码实现有个细节需注意，因为对当前元素排序，这个元素之前是有序表。所以对第i个元素先与第i-1 先比较一下，如果比它大，那就进入下个元素，比它小再放入哨兵，然后找插入的位置，元素后移，再插入。

void print(int a[], int n) {for (int i = 0; i <= n; i++) {cout << a[i] << " ";}cout << endl;
}void sort(int a[], int n) {int i, j;for (int i = 2; i <= n; i++) {if (a[i] <= a[i - 1]) {a[0] = a[i];   //a[0]做存储的哨兵for (j = i - 1; a[0] < a[j]; j--) {a[j + 1] = a[j];}a[j + 1] = a[0];}print(a, n);}
}int main() {int a[9] = {0,49,38,65,97,76,13,27,49 };cout << "初始序列如下，其中第一个元素作为哨兵" << endl;print(a, 8);cout << "下面输出每趟排序后的序列" << endl;sort(a, 8);return 0;
}

3.折半插入排序

~~折半插入排序是对直接插入排序的优化，在查找插入位置的时候。用折半查找比顺序查找性能要好。

void print(int a[], int n) {for (int i = 0; i <= n; i++) {cout << a[i] << " ";}cout << endl;
}void InsertSort(int a[], int n) {int i, j, low,high, mid;for (i = 2; i <= n; i++) {a[0] = a[i];low = 1;high = i-1;while (low <= high) {int mid = (high + low)/2;if (a[0] < a[mid])   high = mid - 1;else   low = mid + 1;}for (j =i-1; j>=high+1; j--) {a[j + 1] = a[j];}a[high + 1] = a[0];print(a, 8);}}
int main() {int a[9] = { 0,49,38,65,97,76,13,27,49 };cout << "初始序列如下，其中第一个元素作为哨兵" << endl;print(a, 8);cout << "下面输出每趟排序后的序列" << endl;InsertSort(a, 8);return 0;
}

4.快速排序

首先还是直观地说，快排其实就是把比它小的往左扔，把比它大的元素往右扔，这样这个元素就排到了它应该在的位置。
~~然后说下具体的算法，第一，怎么实现 “比它小的往左扔，把比它大的元素往右扔”，这里一般情况对数组分割后取第一个元素做排序数，就是在这数组定好最低点Low和最高点High。然后把待排序数赋给另一个辅助空间。先从后向前扫描，只要后面元素比它大，那high–，如果出现比它小的元素，那把小的元素换到low的位置，low++，但这注意这个high的位置是一个“坑”，我们不必每次都交换元素，而是留最后把坑填上。在从low的位置往后扫如果都比它小，则low++。若比它大，就把这个大的元素换过去。在从low往后扫描。如此反复，直到low<high条件不成立为止退出循环。
~还要注意运用递归。因为这是一个“分治法”的运用，上面只是让第一个元素达到它该在的位置，每次排序后都会把数组分割后，数组成倍增长，要对美观数组依次上述排序过程。

int Partition(int a[], int low, int high) {int hhh = a[low];while (low < high) {		while (hhh <a[high]) 	high--;//a[low] = a[high];if (hhh > a[high]) {int temp;temp = a[high];a[high] = hhh;a[low] = temp;low++;  print(a, 8);}while ( hhh > a[low])low++;//a[high] = a[low];if (hhh < a[low]) {int Temp;Temp = a[low];a[low] = hhh;a[high] = Temp;high--; print(a, 8);}}//   a[low] = hhh;//print(a, 8);return low;
}
void quickSort(int a[],int low,int high) {if(low<high){int pivotpos;pivotpos = Partition(a, low, high);quickSort(a, low, pivotpos - 1);quickSort(a, pivotpos + 1, high);}}int main() {int a[8] = { 42,38,65,97,76,13,27,49 };cout << "初始序列如下" << endl;print(a, 8);cout << "下面输出每趟排序后的序列" << endl;quickSort(a, 0,7);print(a, 8);return 0;
}

5.冒泡排序

所谓“冒泡”就是把小的数往上浮（又或者把最大的数往下沉）但把小的数往上排会更好。每相邻的数都会比较一次，这样用一个bool型变量进行判断，若一趟的交换元素，则说明已经是有序的。就直接退出。


void bubbleSort(int a[], int n) {bool flag;int i, j,temp;for (i = 0; i <= n - 1; i++) {flag = 0;for (j = n - 1; j > i; j--) {if (a[j - 1] > a[j]) {temp = a[j];a[j] = a[j - 1];a[j - 1] = temp;flag = 1;}}print(a, n);if (flag == 0)return;}
}
int main() {int a[8] = {42,38,65,97,76,13,27,49};cout << "初始序列如下" << endl;print(a, 8);cout << "下面输出每趟排序后的序列" << endl;bubbleSort(a, 8);//print(a, 8);return 0;
}

6.堆排序

对一个数组来说，大顶堆：需建立每个i<n/2 a[i]>a[2i]&&a[i]>a[2i+1]

大观上看就是建大顶堆——>交换第一个与最后一个元素——>再调整为大顶堆。
其中建大顶堆与调整的算法基本一样。所以算法主要的难点在于调整。

void AdjustDown(int a[], int k,int len)
{a[0] = a[k];int i;for (i=2*k; i < len;i=2*i) {//这个循环是因为如果小，要往//下调接着调if (i < len && a[i] < a[i + 1]) {i++;   //先挑出两个中较大的那个}if (a[0] > a[i])  break;else {a[k] = a[i];k=i;}}a[k] = a[0];print(a, len);
}void Swap(int l[],int a,int b) {int temp = l[b];l[b] = l[a];l[a] = temp;
}void BuildMaxHeap(int a[], int len) {for (int i = len / 2; i > 0; i--) {AdjustDown(a, i, len);}
}void HeapSort(int a[], int n){BuildMaxHeap(a, n);for (int i = n; i > 1; i--) {Swap(a,i,1);AdjustDown(a, 1, i - 1);   //为什么传1,有建大顶堆后//只要调整第一个，一次就能//调最大}
}int main() {int a[11] = {0,503,87,512,61,908,170,897,275,653,426};cout << "初始序列如下，其中第一个元素作为哨兵" << endl;print(a, 10);cout << "下面输出排序后的序列" << endl;HeapSort(a, 10);print(a, 10);return 0;
}

7.归并排序

归并的思想，主要是：递归拆分。将两个有序表合并。
算法的难点也就在于两个表的合并，由于用到了辅助数组，变量较多，需要有清晰的逻辑。

int* b = (int*)malloc((7 + 1) * sizeof(int));
void Merge(int a[], int low, int mid, int high) {int i, j, k;for (k = low; k <= high; k++)b[k] = a[k];for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {if (b[i] <= b[j])a[k] = b[i++];elsea[k] = b[j++];}while (i <= mid)   a[k++] = b[i++];while (j <= high)   a[k++] = b[j++];}
void MergeSort(int a[], int low, int high) {if (low < high) {int mid = (low + high) / 2;MergeSort(a, low, mid);MergeSort(a, mid + 1, high);Merge(a, low, mid, high);print(a, 7);}
}int main() {int a[8] = { 42,38,65,97,76,13,27,49 };cout << "初始序列如下" << endl;print(a, 7);cout << "下面输出每趟排序后的序列" << endl;MergeSort(a,0,7);print(a, 7);return 0;
}

8.希尔排序

希尔排序实际是插入排序的衍生。只是取间隔进行插入排序。具体的好处参见别处啦。主要说代码实现思路。
注意的是这个取间隔排序并不是一趟就排序完，而是逐个往后。比如长度为8的数组或顺序表取间隔 4 应该是1 5 ，2 6 ，3 7 ， 4 8，间隔变2， 1 3， 2 4 ， 1 3 5， 2 4 6 ，1 3 5 7，2 4 6 8。间隔取 1 ，1 2 3 4 5 6 7 8 这样的次序进行插入排序

void sort(int a[], int n) {int i, j, dk;for (dk = n / 2; dk >= 1; dk = dk / 2){cout << "增量为" << dk << "   排序后" << endl;for (i = 1+dk; i <= n; i++) {if (a[i] <= a[i - dk]) {a[0] = a[i];for (j = i - dk; j>0 && a[0]< a[j]; j-=dk) {a[j + dk] = a[j];}a[j + dk] = a[0];}//	print(a, n);}print(a, n);}
}int main() {int a[9] = { 0,49,38,65,97,76,13,27,49 };cout << "初始序列如下，其中第一个元素作为哨兵" << endl;print(a, 8);cout << "下面输出每趟排序后的序列" << endl;sort(a, 8);return 0;
}