这里主要指内部排序，一共是8大算法，5个大类。其中插入、选择、交换分别包含一朴素算法和一改进算法。除了基数排序外，其余四大类都是比较排序。各算法思想在前面几章中已基本讲解，本篇主要是代码实现。
插入排序
直接插入排序
#include <iostream>
using namespace std;
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;
for (i = 1; i < n; i ++) //遍历1～n的元素，检查前面是否有更大的数。因为是从前往后遍历的，所以前1～(i - 1)已经有序。
{
if (a[i] < a[i - 1])
{
int tmp = a[i];
for (j = i - 1; a[j] > tmp && j >= 0; j --) //从后往前向后移
{
a[j + 1] = a[j];
}
a[j + 1] = tmp;
}
}
}
int main()
{
int a[10] = {2,0,3,9,7,4,8,5,6,1};
insertsort(a, 10);
print(a, 10);
return 0;
}
希尔排序
#include <iostream>
using namespace std;
void print(int a[], int n)
{
for (int i = 0; i < n; i ++)
cout<<a[i]<<" ";
cout<<endl;
}
//希尔排序又叫缩小增量排序，在插入排序的基础上分组排序，用增量dk控制排序间隔。
void insertsort(int a[], int n, int dk)
{
int i, j;
for (i = dk; i < n; i ++) //以dk为间隔排序的一趟插入排序
{
if (a[i] < a[i - dk])
{
int tmp = a[i];
for (j = i - dk; a[j] > tmp && j >= 0; j -= dk)
{
a[j + dk] = a[j];
}
a[j + dk] = tmp;
}
}
}
void shellsort(int a[], int n)
{
int dk = n / 2;
while(dk >= 1) //从一半元素开始，一直到增量为1
{
insertsort(a, n, dk);
dk /= 2;
}
}
int main()
{
int a[10] = {2,0,3,9,7,4,8,5,6,1};
shellsort(a, 10);
print(a, 10);
return 0;
}
至于希尔排序为什么能通过增量分组的形式改进插入排序：大概是排序的本质就是消除逆序数，对于随机数组逆序数是O(N^2) ，采用“交换相邻元素”的办法来消除逆序，每次正好只消除一个，因此必须执行O(N^2) 的交换次数，故插入、冒泡的复杂度要到O(N^2)。而交换相隔比较远的元素，可以使一次交换能消除一个以上的逆序，从而提高效率。
选择排序
简单选择排序
#include<algorithm>
#include<iostream>
#include<vector>
#define ll long long
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 mini, mx; //稍作改进，每一趟中同时找最大最小值，这样一趟可以到位两个元素，故外层循环不超过n/2趟
for (int i = 0; i < n/2; i ++)
{
mx = i, mini = i;
for (int j = i + 1; j < n - i; j ++) //1 ~ i与(n - i) ~ (n-1)的最小、最大值部分已到位
{
if (a[j] < a[mini])
mini = j;
if (a[j] > a[mx])
mx = j;
}
swap(a[i], a[mini]);
swap(a[n - 1 - i], a[mx]);
}
}
int main()
{
int a[10] = {0,9,3,7,4,6,2,8,5,1};
selectsort(a, 10);
print(a, 10);
return 0;
}
堆排序
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
void print(int a[], int n)
{
int i;
for (i = 0; i < n; i ++)
cout<<a[i]<<" ";
cout<<endl;
}
//下标从0开始
int Parent(int i)
{
return (i - 1) / 2;
}
int Left(int i)
{
return i * 2 + 1;
}
int Right(int i)
{
return i * 2 + 2;
}
//递归调整位于i的元素
void MaxHeapify(int a [], int n, int i)
{
int l = Left(i);
int r = Right(i);
int largest = 0;
if (l <= (n - 1) && a[l] > a[i])
largest = l;
else
largest = i;
if (r <= (n - 1) && a[r] > a[largest])
largest = r;
if ( largest != i)
{
swap(a[i], a[largest]);
MaxHeapify(a, n, largest);
}
}
void BuildMaxHeap(int a[], int n)
{
int i;
for (i = n / 2 - 1; i >= 0; i --)
MaxHeapify(a, n, i);
}
void HeapSort(int a[], int n)
{
int i;
BuildMaxHeap(a, n);
for (i = n - 1; i >= 1; i --)
{
swap(a[0], a[i]);
MaxHeapify(a, --n, 0);
}
}
int main()
{
int a[10] = {1,0,4,2,9,5,3,8,6,7};
HeapSort(a, 10);
print(a, 10);
return 0;
}
交换排序
冒泡排序
改进处在于设标记pos记录每趟排序后最后一次进行交换的位置，pos之后的记录都已交换到位，每趟排序只要扫描到pos即可。
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
void print(int a[], int n)
{
for (int i = 0; i < n; i ++)
cout<<a[i]<<" ";
cout<<endl;
}
void bubblesort(int a[], int n)
{
int pos;
for (int i = n - 1; i > 0;)
{
pos = 0;
for (int j = 0; j < i; j ++)
if (a[j] > a[j + 1])
{
pos = j;
swap(a[j], a[j + 1]);
}
i = pos;
}
}
int main()
{
int a[10] = {0,9,3,7,4,6,2,8,5,1};
bubblesort(a, 10);
print(a, 10);
return 0;
}
每趟排序中正反向两遍扫描一次得到本趟最大最小两个最终值，使排序趟数减少一半。
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
void print(int a[], int n)
{
for (int i = 0; i < n; i ++)
cout<<a[i]<<" ";
cout<<endl;
}
void bubblesort(int a[], int n)
{
int low = 0, high = n - 1;
while(low < high)
{
for (int j = low; j < high; j ++)
if (a[j] > a[j + 1])
swap(a[j], a[j + 1]);
high --;
for (int j = high; j > low; j --)
if (a[j] < a[j - 1])
swap(a[j], a[j - 1]);
low ++;
}
}
int main()
{
int a[10] = {0,9,3,7,4,6,2,8,5,1};
bubblesort(a, 10);
print(a, 10);
return 0;
}
快速排序
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
void print(int a[], int n)
{
for (int i = 0; i < n; i ++)
cout<<a[i]<<" ";
cout<<endl;
}
int part(int a[], int low, int high)
{
int privote = a[low];
while(low < high)
{
while(low < high && privote <= a[high]) high --;
swap(a[low], a[high]);
while(low < high && privote >= a[low]) low ++;
swap(a[low], a[high]);
}
return low;
}
void quicksort(int a[], int low, int high)
{
if (low < high)
{
int privotloc = part(a, low, high);
quicksort(a, low, privotloc - 1);
quicksort(a, privotloc + 1, high);
}
}
int main()
{
int a[10] = {0,9,3,7,4,6,2,8,5,1};
quicksort(a, 0, 9);
print(a, 10);
return 0;
}
改进：先只对长度大于k的子序列递归调用快排，使原序列基本有序，然后再用插入排序。实践表明k 取为 8左右时性能最佳。
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
void print(int a[], int n)
{
for (int i = 0; i < n; i ++)
cout<<a[i]<<" ";
cout<<endl;
}
int part(int a[], int low, int high)
{
int privote = a[low];
while(low < high)
{
while(low < high && privote <= a[high]) high --;
swap(a[low], a[high]);
while(low < high && privote >= a[low]) low ++;
swap(a[low], a[high]);
}
return low;
}
void qsort_improve(int a[], int low, int high, int k)
{
if (high - low > k)
{
int privotloc = part(a, low, high);
qsort_improve(a, low, privotloc - 1, k);
qsort_improve(a, privotloc + 1, high, k);
}
}
void quicksort(int a[], int n, int k)
{
qsort_improve(a, 0, n - 1, k);
int i, j;
for (i = 1; i < n; i ++)
{
if (a[i] < a[i - 1])
{
int t = a[i];
for (j = i - 1; j >=0 && t < a[j]; j --)
a[j + 1] = a[j];
a[j + 1] = t;
}
}
}
int main()
{
int a[10] = {0,9,3,7,4,6,2,8,5,1};
quicksort(a, 10, 4);
print(a, 10);
return 0;
}
归并排序
第二章已经实现过基本的归并排序，这里主要实现原地归并排序。主要就是以下两幅图的过程，与原归并排序区别在于Merge函数中用到辅助函数convert，将 j 所指的大于 i 所指的部分交换。
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
void print(int a[], int n)
{
for (int i = 0; i < n; i ++)
cout<<a[i]<<" ";
cout<<endl;
}
//用异或实现交换数组中的两数
void swapp(int a[], int x, int y)
{
a[x] ^= a[y];
a[y] ^= a[x];
a[x] ^= a[y];
}
//将数组 l ～ r 间的元素转置
void Reverse(int a[], int l, int r)
{
while (l < r)
swap(a[l ++], a[r --]);
}
//整体交换l ~ mid 和 mid ～ r 部分
void convert(int a[], int l, int mid, int r)
{
Reverse(a, l, mid);
Reverse(a, mid + 1, r);
Reverse(a, l, r);
}
void Merge(int a[], int l, int mid, int r)
{
int i = l;
int j = mid + 1;
while (i < j && j <= r)
{
while (i < j && a[i] <= a[j])
i ++;
int index = j;
while (j <= r && a[j] < a[i])
j ++;
convert(a, i, index - 1, j - 1);
i += j - index;
}
}
void mergesort(int a[], int l, int r)
{
if (l < r)
{
int mid = (l + r) / 2;
mergesort(a, l, mid);
mergesort(a, mid + 1, r);
Merge(a, l, mid, r);
}
}
int main()
{
int a[10] = {0,9,3,7,4,6,2,8,5,1};
mergesort(a, 0, 9);
print(a, 10);
return 0;
}
基数排序
例如对10个三位数排序，先按各位从小到大排，再十位再百位，每次排序可调用桶排序。
