十大排序算法
发现一篇不错的blog，介绍的很清楚，制作了动态图，作者使用的是JS。本人阅读了《经典算法大全》对十大排序重新整理一遍，具体参考原著
转载博客
插入排序（InsertSort） 像是玩朴克一样，我们将牌分作两堆，每次从后面一堆的牌抽出最前端的牌，然后插入前面一
堆牌的适当位置。
Shell排序法 插入排序法由未排序的后半部前端取出一个值，插入已排序前半部的适当位置，概念简单但速度不快。排序要加快的基本原则之一，是让后一次的排序进行时，尽量利用前一次排序后的结果，以加快排序的速度，Shell排序法即是基于此一概念来改良插入排序法。
冒泡排序（BubbleSort） 就是排序时，最大的元素会如同气泡一样移至右端，其利用比较相邻元素的方法，将大的元素交换至右端，所以大的元素会不断的往右移动，直到适当的位置为止。基本的气泡排序法可以利用旗标的方式稍微减少一些比较的时间，当寻访完阵列后都没有发生任何的交换动作，表示排序已经完成，而无需再进行之后的回圈比较与交换动作。
双面排序（ShakerSort） 冒泡排序改进：方法就在于气泡排序的双向进行，先让气泡排序由左向右进行，再来让气泡排序由右往左进行，如此完成一次排序的动作，而您必须使用left与right两个旗标来记录左右两端已排序的元素位置。
选择排序（SelectSort） 将要排序的对象分作两部份，一个是已排序的，一个是未排序的，从后端未排序部份选择一个
最小值，并放入前端已排序部份的最后一个。
堆排序（HeapSort） 选择排序改进：选择排序法的概念简单，每次从未排序部份选一最小值，插入已排序部份的后端，其时间主要花费于在整个未排序部份寻找最小值，如果能让搜寻最小值的方式加 快，选择排序法的速率也就可以加快，Heap排序法让搜寻的路径由树根至最后一个树叶，而不是整个未排序部份，因而称之为改良的选择排序法。
说明快速排序法（QuickSortOne） 是目前所公认最快的排序方法之一（视解题的对象而定），虽然快速排序法在最差状况下可以达O(n2)，但是在多数的情况下，快速排序法的效率表现是相当不错的。快速排序法的基本精神是在数列中找出适当的轴心，然后将数列一分为二，分别对左边与右边数列进行排序，而影响快速排序法效率的正是轴心的选择。这边所介绍的第一个快速排序法版本，是在多数的教科书上所提及的版本，因为它最容易理解，也最符合轴心分割与左右进行排序的概念，适合对初学者进行讲解。
说明快速排序法（QuickSortTwo） 说明在快速排序法（一）中，每次将最左边的元素设为轴，而之前曾经说过，快速排序法的加速在于轴的选择，在这个例子中，只将轴设定为中间的元素，依这个元素作基准进行比较，这可以增加快速排序法的效率。
说明快速排序法（QuickSortThree） 说明之前说过轴的选择是快速排序法的效率关键之一，在这边的快速排序法的轴选择方式更加快了快速排序法的效率，它是来自演算法名书 Introduction to Algorithms 之中。
归并排序，基数排序
#include<iostream>
#define N 10
#define SWAP(x, y) {int temp; temp = x; x = y; y = temp;}
using namespace std;
void BubbleSort(int*);
void ShakerSort(int*);
void SelectSort(int*);
void HeapSort(int*);
void InsertSort(int*);
void ShellSort(int*);
void QuickSortOne(int*,int,int);
void QuickSortTwo(int*);
void QuickSortThree(int*);
int main(int argc, char const *argv[])
{
int arr[] = {1,8,2,34,0,21,5,98,22,11};
//测试函数。
for (int i = 0; i < N; ++i){
cout<<arr[i]<<" ";
}
return 0;
}
//归并排序
void MergeSort(int* arr1, int M, int *arr2, int N, int *arr3 ){
int i = 0, j = 0, k = 0;
while(i < M && j < N){
if(arr1[i] <= arr2[j])
arr3[k++] = arr1[i++];
else
arr3[k++] = arr2[j++];
}
while(i<M)
arr3[k++] = arr1[i++];
while(j<N)
arr3[k++] = arr2[j++];
}
//基数排序
void RadixSort(int *data){
int temp[10][10] = {0};
int order[10] = {0};
int i,j,k,n,lsd;
k = 0;
n = 1;
while(n <= 10){
for(i = 0; i < 10; i++){
lsd = ((data[i] / n) % 10);
temp[lsd][order[lsd]] = data[i];
order[lsd]++;
}
for(i = 0; i < 10; i++){
if(order[i] != 0)
for(j = 0; j < order[i]; j++){
data[k] = temp[i][j];
k++;
}
order[i] = 0;
}
n *= 10;
k = 0;
}
}
void QuickSortOne(int* arr, int left, int right){
int i,j,comp;
if(left < right){
comp = arr[left];
i = left;
j = right + 1;//下面会默认right减一，所以这里先加一处理。
while(1){
while(i + 1 < N && arr[++i] < comp);//向右找
while(j - 1 > -1 && arr[--j] > comp);//向左找
if(i >= j)
break;
SWAP(arr[i],arr[j]);
}
arr[left] = arr[j];
arr[j] = comp;
QuickSortOne(arr, left, j-1);//对左边进行递归
QuickSortOne(arr, j+1, right);//对右边进行递归
}
}
void QuickSortTwo(int* arr, int left, int right){
int i,j,comp;
if(left < right){
comp = arr[(left+right)/2];
i = left - 1;
j = right + 1;
while(1){
//因为轴心在中间了，所以不用判断越界。
while(arr[++i] < comp);
while(arr[--j] > comp);
if(i >= j)
break;
SWAP(arr[i],arr[j]);
}
QuickSortOne(arr, left, j-1);//对左边进行递归
QuickSortOne(arr, j+1, right);//对右边进行递归
}
}
int partition(int *arr, int left, int right){
int i,j,comp;
comp = arr[right];
i = left - 1;
for(j = left; j < right; j++){
if(arr[j] <= comp){
i++;
SWAP(arr[i], arr[j]);
}
}
SWAP(arr[i+1],arr[right]);
return i+1;
}
void QuickSortThree(int* arr, int left, int right){
int q;
if(left < right){
q = partition(arr, left, right);
QuickSortThree(arr, left, q-1);
QuickSortThree(arr, q+1, right);
}
}
void InsertSort(int*){
int i,j,temp;
for (j = 1; i < N; ++j){
temp = arr[i];
i = j - 1;
while(temp < arr[i]){
arr[i+1] = arr[i];
i--;
if(i == -1)
break;
}
arr[i+1] = temp;
}
}
void ShellSort(int* arr){
int i,j,k,gap,t;
gap = N/2;
while(gap > 0){
for(k = 0; k < gap; k++){
for(i = k + gap; i < N; i += gap){
for(j = i - gap; j >= k; j -= gap){
if(arr[j] > arr[j+gap]){
SWAP(arr[j], arr[j+gap])
}
else
break;
}
}
}
gap /= 2;
}
}
void BubbleSort(int* arr){
int i,j,flag = 1;
for ( i = 0; i < N - 1 && flag; ++i){
flag = 0;
for ( j = 0; j < N - i - 1; ++j){
if (arr[j] > arr[j+1]){
SWAP(arr[j],arr[j+1]);
flag = 1;
}
}
}
}
void ShakerSort(int* number){
int i, left = 0, right = N - 1, shift = 0;
while(left < right) {
// 向右进行气泡排序
for(i = left; i < right; i++) {
if(number[i] > number[i+1]) {
SWAP(number[i], number[i+1]);
shift = i; //这个厉害了，记录右边已经有序的坐标，即flag
}
}
right = shift;
printf("\n往右排序：");
for(i = 0; i < N; i++)
printf("%d ", number[i]);
// 向左进行气泡排序
for(i = right; i > left; i--) {
if(number[i] < number[i-1]) {
SWAP(number[i], number[i-1]);
shift = i;
}
}
left = shift;
printf("\n向左排序：");
for(i = 0; i < N; i++)
printf("%d ", number[i]);
}
}
void SelectSort(int* arr){
int i,j,minIndex;
for ( i = 0; i < N - 1; ++i){
minIndex = i;
for ( j = i + 1; j < N; ++j)
if (arr[j] < arr[minIndex])
minIndex = j;
SWAP(arr[i],arr[minIndex])
}
}
void HeapAdjust(int *arr,int i,int length){
int temp = arr[i];//先取出当前元素i
for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
k++;
}
if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
arr[i] = arr[k];
i = k;
}else{
break;
}
}
arr[i] = temp;//将temp值放到最终的位置
}
void HeapSort(int* arr){
int i;
for(i = N/2 - 1; i >= 0; i--)//因为是完全二叉树，所以这是最后面的非叶子节点。
HeapAdjust(arr, i, N);
for (i = N - 1; i > 0; --i){
SWAP(arr[0],arr[i])//这个交换过后，整棵树的长度需要减一，所以下面的i为length - 1。
HeapAdjust(arr,0,i);
}
}