经典排序算法
冒泡排序
冒泡排序(Bubble Sort)，又被称为气泡排序或泡沫排序。
它是一种较简单的排序算法。它会遍历若干次要排序的数列，每次遍历时，它都会从前往后依次的比较相邻两个数的大小；如果前者比后者大，则交换它们的位置。这样，一次遍历之后，最大的元素就在数列的末尾！ 采用相同的方法再次遍历时，第二大的元素就被排列在最大元素之前。重复此操作，直到整个数列都有序为止！
冒泡排序的时间复杂度是O(N2)
假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？N-1次！因此，冒泡排序的时间复杂度是O(N2)。
冒泡排序是稳定的算法，它满足稳定算法的定义
算法稳定性 -- 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！
冒泡排序实现:
public class BubbleSort {
/*
* 冒泡排序
*
* 参数说明：
* a -- 待排序的数组
* n -- 数组的长度
*/
public static void bubbleSort1(int[] a, int n) {
int i,j;
for (i=n-1; i>0; i--) {
// 将a[0...i]中最大的数据放在末尾
for (j=0; j<i; j++) {
if (a[j] > a[j+1]) {
// 交换a[j]和a[j+1]
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
}
/*
* 冒泡排序(改进版)
*
* 参数说明：
* a -- 待排序的数组
* n -- 数组的长度
*/
public static void bubbleSort2(int[] a, int n) {
int i,j;
int flag; // 标记
for (i=n-1; i>0; i--) {
flag = 0; // 初始化标记为0
// 将a[0...i]中最大的数据放在末尾
for (j=0; j<i; j++) {
if (a[j] > a[j+1]) {
// 交换a[j]和a[j+1]
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = 1; // 若发生交换，则设标记为1
}
}
if (flag==0)
break; // 若没发生交换，则说明数列已有序。
}
}
public static void main(String[] args) {
int i;
int[] a = {20,40,30,10,60,50};
System.out.printf("before sort:");
for (i=0; i<a.length; i++){
System.out.printf("%d ", a[i]);
}
System.out.printf("\n");
bubbleSort1(a, a.length);
//bubbleSort2(a, a.length);
System.out.printf("after sort:");
for (i=0; i<a.length; i++){
System.out.printf("%d ", a[i]);
}
System.out.printf("\n");
}
}结果:
before sort: 20 40 30 10 60 50
after sort: 10 20 30 40 50 60
选择排序
选择排序(Selection sort)是一种简单直观的排序算法。
它的基本思想是：首先在未排序的数列中找到最小(or最大)元素，然后将其存放到数列的起始位置；接着，再从剩余未排序的元素中继续寻找最小(or最大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的时间复杂度是O(N2)
选择排序是稳定的算法，它满足稳定算法的定义
public class SelectSort {
/*
* 选择排序
*
* 参数说明：
* a -- 待排序的数组
* n -- 数组的长度
*/
public static void selectSort(int[] a, int n) {
int i; // 有序区的末尾位置
int j; // 无序区的起始位置
int min; // 无序区中最小元素位置
for(i=0; i<n; i++) {
min=i;
// 找出"a[i+1] ... a[n]"之间的最小元素，并赋值给min。
for(j=i+1; j<n; j++) {
if(a[j] < a[min])
min=j;
}
// 若min!=i，则交换 a[i] 和 a[min]。
// 交换之后，保证了a[0] ... a[i] 之间的元素是有序的。
if(min != i) {
int tmp = a[i];
a[i] = a[min];
a[min] = tmp;
}
}
}
public static void main(String[] args) {
int i;
int[] a = {20,40,30,10,60,50};
System.out.printf("before sort:");
for (i=0; i<a.length; i++)
System.out.printf("%d ", a[i]);
System.out.printf("\n");
selectSort(a, a.length);
System.out.printf("after sort:");
for (i=0; i<a.length; i++)
System.out.printf("%d ", a[i]);
System.out.printf("\n");
}
}结果:
before sort: 20 40 30 10 60 50
after sort: 10 20 30 40 50 60
快速排序
快速排序(Quick Sort)使用分治法策略。
它的基本思想是：选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序流程：
1. 从数列中挑出一个基准值。
2. 将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)；在这个分区退出之后，该基准就处于数列的中间位置。
3. 递归地把"基准值前面的子数列"和"基准值后面的子数列"进行排序。
快速排序是不稳定的算法，它不满足稳定算法的定义。
快速排序的时间复杂度在最坏情况下是O(N2)，平均的时间复杂度是O(N*lgN)。
这句话很好理解：假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N)，需要遍历多少次呢？至少lg(N+1)次，最多N次。
(1)为什么最少是lg(N+1)次？快速排序是采用的分治法进行遍历的，我们将它看作一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(N+1)。因此，快速排序的遍历次数最少是lg(N+1)次。
(2)为什么最多是N次？这个应该非常简单，还是将快速排序看作一棵二叉树，它的深度最大是N。因此，快读排序的遍历次数最多是N次。
public class QuickSort {
/*
* 快速排序
*
* 参数说明：
* a -- 待排序的数组
* l -- 数组的左边界(例如，从起始位置开始排序，则l=0)
* r -- 数组的右边界(例如，排序截至到数组末尾，则r=a.length-1)
*/
public static void quickSort(int[] a, int l, int r) {
if (l < r) {
int i,j,x;
i = l;
j = r;
x = a[i];
while (i < j) {
while(i < j && a[j] > x)
j--; // 从右向左找第一个小于x的数
if(i < j)
a[i++] = a[j];
while(i < j && a[i] < x)
i++; // 从左向右找第一个大于x的数
if(i < j)
a[j--] = a[i];
}
a[i] = x;
quickSort(a, l, i-1); /* 递归调用 */
quickSort(a, i+1, r); /* 递归调用 */
}
}
public static void main(String[] args) {
int i;
int a[] = {30,40,60,10,20,50};
System.out.printf("before sort:");
for (i=0; i<a.length; i++)
System.out.printf("%d ", a[i]);
System.out.printf("\n");
quickSort(a, 0, a.length-1);
System.out.printf("after sort:");
for (i=0; i<a.length; i++)
System.out.printf("%d ", a[i]);
System.out.printf("\n");
}
}结果:
before sort:30 40 60 10 20 50
after sort: 10 20 30 40 50 60
归并排序
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。
合并相邻有序子序列
再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。
public class MergeSort {
public static void main(String []args){
int []arr = {9,8,7,6,5,4,3,2,1};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int []arr){
int []temp = new int[arr.length];
//在排序前，先建好一个长度等于原数组长度的临时数组，
//避免递归中频繁开辟空间
sort(arr,0,arr.length-1,temp);
}
private static void sort(int[] arr,int left,int right,int []temp){
if(left<right){
int mid = (left+right)/2;
sort(arr,left,mid,temp);
//左边归并排序，使得左子序列有序
sort(arr,mid+1,right,temp);
//右边归并排序，使得右子序列有序
merge(arr,left,mid,right,temp);
//将两个有序子数组合并操作
}
}
private static void merge(int[] arr,int left,int mid,int right,int[] temp){
int i = left;//左序列指针
int j = mid+1;//右序列指针
int t = 0;//临时数组指针
while (i<=mid && j<=right){
if(arr[i]<=arr[j]){
temp[t++] = arr[i++];
}else {
temp[t++] = arr[j++];
}
}
while(i<=mid){//将左边剩余元素填充进temp中
temp[t++] = arr[i++];
}
while(j<=right){//将右序列剩余元素填充进temp中
temp[t++] = arr[j++];
}
t = 0;
//将temp中的元素全部拷贝到原数组中
while(left <= right){
arr[left++] = temp[t++];
}
}
}结果:
[1, 2, 3, 4, 5, 6, 7, 8, 9]
最后:
归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。
直接插入排序
直接插入排序(Straight Insertion Sort)的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。
下面选取直接插入排序的一个中间过程对其进行说明。假设{20,30,40,10,60,50}中的前3个数已经排列过，是有序的了；接下来对10进行排列。示意图如下：
图中将数列分为有序区和无序区。我们需要做的工作只有两个：(1)取出无序区中的第1个数，并找出它在有序区对应的位置。(2)将无序区的数据插入到有序区；若有必要的话，则对有序区中的相关数据进行移位。
直接插入排序的时间复杂度是O(N2)。
直接插入排序是稳定的算法，它满足稳定算法的定义。
public class InsertSort {
/*
* 直接插入排序
*
* 参数说明：
* a -- 待排序的数组
* n -- 数组的长度
*/
public static void insertSort(int[] a, int n) {
int i, j, k;
for (i = 1; i < n; i++) {
//为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置
for (j = i - 1; j >= 0; j--)
if (a[j] < a[i])
break;
//如找到了一个合适的位置
if (j != i - 1) {
//将比a[i]大的数据向后移
int temp = a[i];
for (k = i - 1; k > j; k--)
a[k + 1] = a[k];
//将a[i]放到正确位置上
a[k + 1] = temp;
}
}
}
public static void main(String[] args) {
int i;
int[] a = {20,40,30,10,60,50};
System.out.printf("before sort:");
for (i=0; i<a.length; i++)
System.out.printf("%d ", a[i]);
System.out.printf("\n");
insertSort(a, a.length);
System.out.printf("after sort:");
for (i=0; i<a.length; i++)
System.out.printf("%d ", a[i]);
System.out.printf("\n");
}
}结果:
before sort:20 40 30 10 60 50
after sort: 10 20 30 40 50 60
希尔排序
希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。
把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。
随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。
我们来通过演示图，更深入的理解一下这个过程。
在上面这幅图中：
初始时，有一个大小为 10 的无序序列。
在第一趟排序中，我们不妨设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。接下来，按照直接插入排序的方法对每个组进行排序。
在第二趟排序中，我们把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。按照直接插入排序的方法对每个组进行排序。
在第三趟排序中，再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。
需要注意一下的是，图中有两个相等数值的元素 5 和 5 。我们可以清楚的看到，在排序过程中，两个元素位置交换了。
所以，希尔排序是不稳定的算法。
public void shellSort(int[] list) {
int gap = list.length / 2;
while (1 <= gap) {
// 把距离为 gap 的元素编为一个组，扫描所有组
for (int i = gap; i < list.length; i++) {
int j = 0;
int temp = list[i];
// 对距离为 gap 的元素组进行排序
for (j = i - gap; j >= 0 && temp < list[j]; j = j - gap) {
list[j + gap] = list[j];
}
list[j + gap] = temp;
}
System.out.format("gap = %d:\t", gap);
printAll(list);
gap = gap / 2; // 减小增量
}
}
希尔排序的算法性能
时间复杂度
步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。
算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为插入排序，这就保证了数据一定会被排序。
Donald Shell 最初建议步长选择为N/2并且对步长取半直到步长达到1。虽然这样取可以比O(N2)类的算法（插入排序）更好，但这样仍然有减少平均时间和最差时间的余地。
可能希尔排序最重要的地方在于当用较小步长排序后，以前用的较大步长仍然是有序的。比如，如果一个数列以步长5进行了排序然后再以步长3进行排序，那么该数列不仅是以步长3有序，而且是以步长5有序。如果不是这样，那么算法在迭代过程中会打乱以前的顺序，那就不会以如此短的时间完成排序了。
已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,...)，该序列的项来自这两个算式。
这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长序列的希尔排序比插入排序和堆排序都要快，甚至在小数组中比快速排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。
算法稳定性
由上文的希尔排序算法演示图即可知，希尔排序中相等数据可能会交换位置，所以希尔排序是不稳定的算法。
直接插入排序和希尔排序的比较
1. 直接插入排序是稳定的；而希尔排序是不稳定的。
2. 直接插入排序更适合于原始记录基本有序的集合。
3. 希尔排序的比较次数和移动次数都要比直接插入排序少，当N越大时，效果越明显。
4. 在希尔排序中，增量序列gap的取法必须满足：最后一个步长必须是 1 。
5. 直接插入排序也适用于链式存储结构；希尔排序不适用于链式结构。
代码实现:
public class ShellSort {
public void shellSort(int[] list) {
int gap = list.length / 2;
while (1 <= gap) {
// 把距离为 gap 的元素编为一个组，扫描所有组
for (int i = gap; i < list.length; i++) {
int j = 0;
int temp = list[i];
// 对距离为 gap 的元素组进行排序
for (j = i - gap; j >= 0 && temp < list[j]; j = j - gap) {
list[j + gap] = list[j];
}
list[j + gap] = temp;
}
System.out.format("gap = %d:\t", gap);
printAll(list);
gap = gap / 2; // 减小增量
}
}
// 打印完整序列
public void printAll(int[] list) {
for (int value : list) {
System.out.print(value + "\t");
}
System.out.println();
}
public static void main(String[] args) {
int[] array = {
9, 1, 2, 5, 7, 4, 8, 6, 3, 5
};
// 调用希尔排序方法
ShellSort shell = new ShellSort();
System.out.print("排序前:\t\t");
shell.printAll(array);
shell.shellSort(array);
System.out.print("排序后:\t\t");
shell.printAll(array);
}
}结果:
排序前: 9 1 2 5 7 4 8 6 3 5
gap = 5: 4 1 2 3 5 9 8 6 5 7
gap = 2: 2 1 4 3 5 6 5 7 8 9
gap = 1: 1 2 3 4 5 5 6 7 8 9
排序后: 1 2 3 4 5 5 6 7 8 9
基数排序
基数排序不需要比较关键字的大小。
它是根据关键字中各位的值，通过对排序的N个元素进行若干趟“分配”与“收集”来实现排序的。
不妨通过一个具体的实例来展示一下，基数排序是如何进行的。 设有一个初始序列为: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。
我们知道，任何一个阿拉伯数，它的各个位数上的基数都是以0~9来表示的。所以我们不妨把0~9视为10个桶。
我们先根据序列的个位数的数字来进行分类，将其分到指定的桶中。例如：R[0] = 50，个位数上是0，将这个数存入编号为0的桶中。
分类后，我们在从各个桶中，将这些数按照从编号0到编号9的顺序依次将所有数取出来。这时，得到的序列就是个位数上呈递增趋势的序列。
按照个位数排序： {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。接下来，可以对十位数、百位数也按照这种方法进行排序，最后就能得到排序完成的序列。
时间复杂度
通过上文可知，假设在基数排序中，r为基数，d为位数。则基数排序的时间复杂度为O(d(n+r))。我们可以看出，基数排序的效率和初始序列是否有序没有关联。
空间复杂度
在基数排序过程中，对于任何位数上的基数进行“装桶”操作时，都需要n+r个临时空间。
算法稳定性
在基数排序过程中，每次都是将当前位数上相同数值的元素统一“装桶”，并不需要交换位置。所以基数排序是稳定的算法。
基数排序的性能
LSD法实现:
public class RadixSort {
// 获取x这个数的d位数上的数字
// 比如获取123的1位数，结果返回3
public int getDigit(int x, int d) {
int a[] = {
1, 1, 10, 100
}; // 本实例中的最大数是百位数，所以只要到100就可以了
return ((x / a[d]) % 10);
}
public void radixSort(int[] list, int begin, int end, int digit) {
final int radix = 10; // 基数
int i = 0, j = 0;
int[] count = new int[radix]; // 存放各个桶的数据统计个数
int[] bucket = new int[end - begin + 1];
// 按照从低位到高位的顺序执行排序过程
for (int d = 1; d <= digit; d++) {
// 置空各个桶的数据统计
for (i = 0; i < radix; i++) {
count[i] = 0;
}
// 统计各个桶将要装入的数据个数
for (i = begin; i <= end; i++) {
j = getDigit(list[i], d);
count[j]++;
}
// count[i]表示第i个桶的右边界索引
for (i = 1; i < radix; i++) {
count[i] = count[i] + count[i - 1];
}
// 将数据依次装入桶中
// 这里要从右向左扫描，保证排序稳定性
for (i = end; i >= begin; i--) {
j = getDigit(list[i], d);
// 求出关键码的第k位的数字， 例如：576的第3位是5
bucket[count[j] - 1] = list[i];
// 放入对应的桶中，count[j]-1是第j个桶的右边界索引
count[j]--; // 对应桶的装入数据索引减一
}
// 将已分配好的桶中数据再倒出来，此时已是对应当前位数有序的表
for (i = begin, j = 0; i <= end; i++, j++) {
list[i] = bucket[j];
}
}
}
public int[] sort(int[] list) {
radixSort(list, 0, list.length - 1, 3);
return list;
}
// 打印完整序列
public void printAll(int[] list) {
for (int value : list) {
System.out.print(value + "\t");
}
System.out.println();
}
public static void main(String[] args) {
int[] array = {
50, 123, 543, 187, 49, 30, 0, 2, 11, 100
};
RadixSort radix = new RadixSort();
System.out.print("排序前:\t\t");
radix.printAll(array);
radix.sort(array);
System.out.print("排序后:\t\t");
radix.printAll(array);
}
}运行结果:
排序前: 50 123 543 187 49 30 0 2 11 100
排序后: 0 2 11 30 49 50 100 123 187 543