程序员必须掌握的8大排序算法
分类： 1）插入排序（直接插入排序、希尔排序） 2）交换排序（冒泡排序、快速排序） 3）选择排序（直接选择排序、堆排序） 4）归并排序 5）分配排序（基数排序）
sort.jpg
一、直接插入排序
（一）基本思想
在要排序的一组数中，假设前面(n-1)[n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
1-1.jpg
（二）代码实现（Java）
import java.util.Arrays;
public class Sort {
public static void insertSort(int[] array) {
int i, j, temp;
for (i = 1; i < array.length; i++) {
temp = array[i];
j = i;
// 将大于temp的值整体后移一个单位
while(j > 0 && array[j-1] > temp)
{
array[j] = array[j-1];
j--;
}
array[j]=temp;
}
}
public static void main(String[] args) {
int[] arr = {57, 68, 59, 52};
System.out.println("Original array: " + Arrays.toString(arr));
insertSort(arr);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}运行结果：
Original array: [57, 68, 59, 52]
Sorted array: [52, 57, 59, 68]程序分析： for循环中， （1） i = 1, temp = a[1] = 68, j = 1, array[0] = 57, array[0] > temp不成立，不需要调整
（2）i = 2，temp = a[2] = 59， ① j = 2，array[1] = 68 > temp，执行循环array[2] = array[1] = 68，j自减。 ② j = 1, array[0] = 57 > temp不成立，循环结束。 ③ 最后执行array[1] = temp = 59，此时arr = {57，59，68，52}
（3）i = 3，temp = a[3] = 52 ① j = 3, array[2] = 68 > temp，执行循环array[3] = array[2] = 68，j自减 ② j = 2，array[1] = 59 > temp，执行循环array[2] = array[1] = 59，j自减 ③ j = 1，array[0] = 57 > temo，执行循环array[1] = array[0] = 57，j自减后变为0，循环结束 ④ 最后执行array[0] = temp = 52，此时array = {52, 57, 59, 68}
二、希尔排序
（一）基本思想
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
（二）例子
有一个数组，其原始数组为：
2-1.png
取初始增量gap = length / 2 = 5，这样就将整个数组分为5组（每组用相同的颜色表示）
2-2.png
将这5组的数据分别按由小到大的顺序排列，结果为
2-3.png
缩小增量gap = gap / 2 = 2，整个数组被分成两组
2-4.png
将这两组的数据分别按由小到大的顺序排列，结果为
2-5.png
再次缩小增量，整个数组被分为1组
2-6.png
将这组数据按从小到大的顺序排序，最终结果为
2-7.png
（三）代码
1 C语言实现
#include<stdio.h>
void swap(int &a, int &b)
{
a ^= b;
b ^= a;
a ^= b;
}
void shellsort(int a[], int n)
{
int i, j, gap;
for (gap = n / 2; gap > 0; gap /= 2)
for (i = gap; i < n; i++)
for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)
swap(a[j], a[j + gap]);
}
void main()
{
int arr[] = {49, 38, 65, 97, 76, 13, 27, 48, 55, 4};
printf("Original array: ");
int i;
int len = sizeof(arr)/sizeof(int);
for(i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
shellsort(arr, len);
printf("Sorted array: ");
for(i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}2 Java实现
package com.z;
import java.util.Arrays;
public class Sort {
public static void shellSort(int[] array) {
int i, j, gap;
int len = array.length;
for (gap = len / 2; gap > 0; gap /= 2) {
for (i = gap; i < len; i++) {
for (j = i - gap; j >= 0 && array[j] > array[j + gap]; j -= gap) {
// 交换 两个数
array[j] ^= array[j + gap];
array[j + gap] ^= array[j];
array[j] ^= array[j + gap];
}
}
}
}
public static void main(String[] args) {
int[] arr = {49, 38, 65, 97, 76, 13, 27, 48, 55, 4};
System.out.println("Original array: " + Arrays.toString(arr));
shellSort(arr);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}3 运行结果
Original array: [49, 38, 65, 97, 76, 13, 27, 48, 55, 4]
Sorted array: [4, 13, 27, 38, 48, 49, 55, 65, 76, 97]三、简单选择排序
（一）基本原理（由小到大）
先将n个数中最小的数与a[0]对换，再将a[1]到a[n-1]中最小的数与a[1]对换
每比较一轮，找出未经排序的数中最小的一个。共比较n-1轮。
3-1.jpg
（二）编程实现
1 Java实现
package com.z;
import java.util.Arrays;
public class Sort {
public static void selectSort(int[] array) {
int j, minIndex;
for (int i = 0; i < array.length - 1; i++) {
minIndex = i;
for (j = i + 1; j < array.length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
if(minIndex != i) {
array[minIndex] ^= array[i];
array[i] ^= array[minIndex];
array[minIndex] ^= array[i];
}
}
}
public static void main(String[] args) {
int[] arr = {57, 68, 59, 52};
System.out.println("Original array: " + Arrays.toString(arr));
selectSort(arr);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}运行结果：
Original array: [57, 68, 59, 52]
Sorted array: [52, 57, 59, 68]2 C语言实现
#include<stdio.h>
void select_sort(int a[],int n)
{
int i, j, min;
for(i = 0; i < n - 1; i++)
{
min = i;
for(j = i + 1; j < n; j++)
{
if(a[j] < a[min])
{
min = j;
}
}
if(min != i)
{
a[min] = a[min] ^ a[i];
a[i] = a[min] ^ a[i];
a[min] = a[min] ^ a[i];
}
}
}
int main()
{
int b[] = {5, 4, 3, 2, 1};
int len = sizeof(b) / sizeof(int);
select_sort(b, len);
for(int i = 0; i < len; i++)
{
printf("%d ",b[i]);
}
printf("\n");
return 0;
}运行结果：
1 2 3 4 53 C++函数模板实现
#include <iostream>
using namespace std;
#ifndef ARRAY_BASED_SORTING_FUNCTIONS
#define ARRAY_BASED_SORTING_FUNCTIONS
template<class T>
void Swap(T &x, T &y)
{
x = x ^ y;
y = x ^ y;
x = x ^ y;
}
template<class T>
void SelectionSort(T a[], int n)
{
int i, j, min;
for(i = 0; i < n-1; i++)
{
min = i;
for(j = i + 1; j < n; j++)
{
if(a[j] < a[min])
{
min = j;
}
}
if(min != i)
{
Swap(a[i], a[min]);
}
}
}
#endif
int main()
{
int a[] = {14, 12, 10, 8, 11, 4, 2};
int len = sizeof(a) / sizeof(int);
SelectionSort(a, len);
for (int i = 0; i < len; i++)
{
cout << a[i] << ' ';
}
cout << endl;
return 0;
}运行结果：
2 4 8 10 11 12 14四、堆排序
（一）什么是堆
堆实际上是一棵完全二叉树，其任何一非叶节点满足性质： Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者 Key[i]>=Key[2i+1]&&key>=key[2i+2]， 即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。 堆分为大顶堆和小顶堆，满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆，满足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。
（二）堆排序思想
利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。 以大顶堆为例，其基本思想为： a）将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区； b）将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]; c）由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2，……，Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
（三）操作过程
a）初始化堆：将R[1..n]构造为堆； b）将当前无序区的堆顶元素R[1]同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。 因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。
（四）例子和代码
针对两步操作过程，咱们以整形数组a[]={16,7,3,20,17,8}为例。 a）第一步是构造初始堆： 首先根据该数组元素构建一个完全二叉树，得到
4-1.jpg
然后需要构造初始堆，则从最后一个非叶节点开始调整，调整过程如下：
4-2.jpg
4-3.jpg
4-4.jpg 上图中因为16，7，17三个节点不满足堆的性质，因此需要重新调整如下图：
4-5.jpg
这样就得到了初始堆。 上面的过程实际上就是每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换，交换之后可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整。 整个过程的实现代码如下：
#include <stdio.h>
void HeapAdjust(int *a,int i,int size) //调整堆
{
// 如果i是叶子 节点就不用进行调整
if(i >= size/2)
{
return;
}
// i非叶子节点，开始调整
int lchild = 2 * i + 1; // i的左孩子节点序号
int rchild = 2 * i + 2; // i的右孩子节点序号
int max = i; // 临时变量
if(lchild < size && a[lchild] > a[max])
{
max = lchild;
}
if(rchild < size && a[rchild] > a[max])
{
max = rchild;
}
if(max != i)
{
// 将a[i]与a[max]对换
a[i] = a[i] ^ a[max];
a[max] = a[i] ^ a[max];
a[i] = a[i] ^ a[max];
// 若调整之后以max为父节点的子树不是堆，则对该子树继续调整
HeapAdjust(a, max, size);
}
}
void BuildHeap(int *a,int size)
{
for(int i = size/2 - 1; i >= 0; i--) //非叶节点最大序号值为size/2
{
HeapAdjust(a, i, size);
}
}
int main(int argc, const char * argv[])
{
int a[] = {16, 7, 3, 20, 17, 8};
int size = sizeof(a) / sizeof(int);
BuildHeap(a, size); // 建立堆
printf("构造出初始堆");
for(int i = 0; i < size; i++)
{
printf("%d ", a[i]);
}
return 0;
}运行结果：
构造出初始堆 20 17 8 7 16 3b）有了初始堆之后，就可以进行排序
4-6.jpg
此时3位于堆顶不满足堆的性质需要继续调整：
4-7.jpg
调整后，3、7、16这个子堆不满足堆的性质，继续调整：
4-8.jpg
这样经过第一轮调整后，得到了一个有序数组{20}和一个调整后的堆。下面继续调整：
4-9.jpg
4-10.jpg
4-11.jpg
这样经过第二轮调整后，得到一个有序数组{17，20}和一个调整后的堆。继续调整：
4-12.jpg
4-13.jpg
这样经过第三轮调整后，得到一个有序数组{16，17，20}和一个调整后的堆。继续调整：
4-14.jpg
4-15.jpg
这样经过第四轮调整后，得到一个有序数组{8，16，17，20}和一个调整后的堆。继续调整：
4-16.jpg
这样经过第五轮调整后，得到一个有序数组{7，8，16，17，20}和一个调整后的堆，这个堆只有一个元素，且一定是整个数组中的最小值，所以不用调整。 由上述过程可知，总共需要调整5轮，即sizeof(数组)-1轮。
下面给出实现的代码：
#include <stdio.h>
void HeapAdjust(int *a,int i,int size) //调整堆
{
// 如果i是叶子 节点就不用进行调整
if(i >= size/2)
{
return;
}
// i非叶子节点，开始调整
int lchild = 2 * i + 1; // i的左孩子节点序号
int rchild = 2 * i + 2; // i的右孩子节点序号
int max = i; // 临时变量
if(lchild < size && a[lchild] > a[max])
{
max = lchild;
}
if(rchild < size && a[rchild] > a[max])
{
max = rchild;
}
if(max != i)
{
// 将a[i]与a[max]对换
a[i] = a[i] ^ a[max];
a[max] = a[i] ^ a[max];
a[i] = a[i] ^ a[max];
// 若调整之后以max为父节点的子树不是堆，则对该子树继续调整
HeapAdjust(a, max, size);
}
}
void BuildHeap(int *a,int size)
{
for(int i = size/2 - 1; i >= 0; i--) //非叶节点最大序号值为size/2
{
HeapAdjust(a, i, size);
}
}
void HeapSort(int *a,int size) //堆排序
{
BuildHeap(a, size);
for(int i = size - 1; i > 0; i--)
{
// 交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面
a[i] = a[i] ^ a[0];
a[0] = a[i] ^ a[0];
a[i] = a[i] ^ a[0];
HeapAdjust(a, 0, i); //重新调整堆顶节点成为大顶堆
}
}
int main(int argc, const char * argv[])
{
int a[] = {16, 7, 3, 20, 17, 8};
int size = sizeof(a) / sizeof(int);
HeapSort(a, size); // 堆排序
printf("堆排序后的结果 ");
for(int i = 0; i < size; i++)
{
printf("%d ", a[i]);
}
return 0;
}运行结果：
堆排序后的结果 3 7 8 16 17 20（五） 进一步分析
从上述过程可知，堆排序其实也是一种选择排序，是一种树形选择排序。只不过直接选择排序中，为了从R[1…n]中选择最大记录，需比较n-1次，然后从R[1…n-2]中选择最大记录需比较n-2次。事实上这n-2次比较中有很多已经在前面的n-1次比较中已经做过，而树形选择排序恰好利用树形的特点保存了部分前面的比较结果，因此可以减少比较次数。对于n个关键字序列，最坏情况下每个节点需比较log2(n)次，因此其最坏情况下时间复杂度为nlogn。堆排序为不稳定排序，不适合记录较少的排序。
五、冒泡排序
（一）基本原理（由小到大）：
将相邻两个数比较，将大的调到后头。如果有n个数，则要进行n-1趟比较。
在第1趟中要进行n-1次两两比较，在第j趟比较中要进行n-j次两两比较。
5-1.png
（二）代码实现
1 C语言实现
#include <stdio.h>
void bubbleSort(int a[], int n)
{
for(int round = 0; round < n - 1; round++)
{
for(int i = 0; i < n - 1 - round; i++)
{
if(a[i] > a[i+1])
{
a[i] = a[i] ^ a[i+1];
a[i+1] = a[i] ^ a[i+1];
a[i] = a[i] ^ a[i+1];
}
}
}
}
int main()
{
int a[5] = {5, 3, 4, 1, 2};
bubbleSort(a, 5);
for (int i = 0; i < 5; i++)
{
printf("%d ", a[i]);
}
return 0;
}运行结果：
1 2 3 4 5 2 C++函数模板实现
#include <iostream>
using namespace std;
#ifndef ARRAY_BASED_SORTING_FUNCTIONS
#define ARRAY_BASED_SORTING_FUNCTIONS
template<class T>
void Swap(T &x,T &y)
{
T temp;
temp=x;
x=y;
y=temp;
}
template<class T> void BubbleSort(T A[],int n)
{
int i,j;
int lastExchangeIndex;
i=n-1;
while(i>0)
{
lastExchangeIndex=0;
for(j=0;j<i;j++)
{
if(A[j+1]<A[j])
{
Swap(A[j],A[j+1]);
lastExchangeIndex=j;
}
}
i=lastExchangeIndex;
}
}
#endif
int main()
{
int a[] = {57, 68, 59, 52};
int len = sizeof(a) / sizeof(int);
BubbleSort(a, len);
for (int i = 0; i < len; i++)
{
cout << a[i] << ' ';
}
cout << endl;
return 0;
}运行结果：
52 57 59 68六、快速排序
（一）基本思想
选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
（二）例子
6-1.png
以{5, 9, 2, 7 ,8, 3, 6, 1, 4, 0}为例。选择第0个元素5作为参照数，咱们第一步的目标是把比5小的数都调整到5的左边，比5大的数都调到5的右边。 （1）从左往右开始观察，发现9比5大，准备调整。再从右往左观察，发现0比5小，准备调整。对调9和0的位置。 （2）继续从左往右观察，2比5小，不用调。继续往右，7比5大，准备调整。继续从右往左观赛，4比5小，准备调整。对调7和4的位置。 （3）继续从左往右观察，8比5大，准备调整。继续从右往左观察，1比5小，准备调整。对调8和1的位置。 （4）继续从左往右观察，3比5小，不用调整。继续往右观察，碰到6，准备调整。继续从右往左观察，第一个碰到的就是6，这时从左往右或者从右往左碰到的都是6，所以6不用调，也不需要再继续观察下去了。 （5）最后一次调整一下3和5的位置。得到了第一步的目标，比5小的{3, 0, 2, 4, 1}都在5的左边，比5大的{6, 8, 7, 9}都在5的右边。 （6）对新数列{3, 0, 2, 4, 1}和{6, 8, 7, 9}分别用上面的方法继续调整，直到所有的数都排完序为止。
（三）C++代码实现
#include <iostream>
using namespace std;
void QuickSort(int a[], int low, int high)
{
if(low >= high)
{
return;
}
int pivot = a[low];
int i = low + 1;
int j = high;
while(i <= j)
{
if(a[i] <= pivot)
{
i++;
}
else if(a[j] > pivot)
{
j--;
}
else
{
// swap a[i], a[j]
a[i] = a[i] ^ a[j];
a[j] = a[i] ^ a[j];
a[i] = a[i] ^ a[j];
i++;
j--;
}
}
// swap a[low] , a[j]
a[low] = a[j];
a[j] = pivot;
j--;
QuickSort(a, low, j);
QuickSort(a, i, high);
}
void PrintArrary(int data[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << data[i] << " ";
}
cout << endl;
}
int main(int argc, const char** argv)
{
int array[]= {5, 9, 2, 7, 8, 3, 6, 1, 4, 0};
int size = sizeof(array)/sizeof(int);
QuickSort(array, 0, size - 1);
PrintArrary(array, size);
return 0;
}运行结果：
0 1 2 3 4 5 6 7 8 9七、归并排序
（一）基本思想
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
7-1.jpg
（二）代码实现
package com.z;
import java.util.Arrays;
public class Sort {
public static void mergeSort(int[] array) {
sort(array, 0, array.length - 1);
}
private static void sort(int[] data, int left, int right) {
if (left < right) {
// 找出中间索引
int center = (left + right) / 2;
// 对左边数组进行递归
sort(data, left, center);
// 对右边数组进行递归
sort(data, center + 1, right);
// 合并
merge(data, left, center, right);
}
}
private static void merge(int[] data, int left, int center, int right) {
int[] tmpArr = new int[data.length];
int centerNext = center + 1;
// 记录临时数组的索引
int tmp = left;
int index = left;
while (left <= center && centerNext <= right) {
//从两个数组中取出最小的放入临时数组
if (data[left] <= data[centerNext]) {
tmpArr[tmp++] = data[left++];
} else {
tmpArr[tmp++] = data[centerNext++];
}
}
// 若右边数组还有剩余元素，把这些剩余元素依次放入临时数组
while (centerNext <= right) {
tmpArr[tmp++] = data[centerNext++];
}
// 若左边数组还有剩余元素，把这些剩余元素依次放入临时数组
while (left <= center) {
tmpArr[tmp++] = data[left++];
}
// 将临时数组中的内容复制回原数组
while (index <= right) {
data[index] = tmpArr[index++];
}
}
public static void main(String[] args) {
int[] arr = {52, 57, 59, 68, 28, 33, 72, 96};
System.out.println("Original array: " + Arrays.toString(arr));
mergeSort(arr);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}运行结果：
Original array: [52, 57, 59, 68, 28, 33, 72, 96]
Sorted array: [28, 33, 52, 57, 59, 68, 72, 96]八、基数排序
（一）基本思想
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位（即个位数）开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
8-1.jpg
（二）代码实现
package com.z;
import java.util.ArrayList;
import java.util.Arrays;
public class Sort {
public static void radixSort(int[] array) {
//获取最大的数
int max = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
}
int digitCount = 0;
//判断位数，位数即排序的趟数
while (max > 0) {
max /= 10;
digitCount++;
}
//建立10个数组;
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
for (int i = 0; i < 10; i++) {
ArrayList<Integer> list1 = new ArrayList<>();
list.add(list1);
}
//进行digitCount次分配和收集;
for (int i = 0; i < digitCount; i++) {
//分配数组元素;
for (int num : array) {
//得到数字的第i+1位数;
int x = num % (int)Math.pow(10, i + 1) / (int)Math.pow(10, i);
ArrayList<Integer> list2 = list.get(x);
list2.add(num);
list.set(x, list2);
}
int index = 0;
//重新排列数组中的元素
for (int k = 0; k < 10; k++) {
while (list.get(k).size() > 0) {
ArrayList<Integer> list3 = list.get(k);
array[index] = list3.get(0);
list3.remove(0);
index++;
}
}
}
}
public static void main(String[] args) {
int[] arr = {135, 242, 192, 93, 345, 11, 24, 19};
System.out.println("Original array: " + Arrays.toString(arr));
radixSort(arr);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}运行结果：
Original array: [135, 242, 192, 93, 345, 11, 24, 19]
Sorted array: [11, 19, 24, 93, 135, 192, 242, 345]