本文介绍各种排序算法的基本思想，时间复杂度和稳定性，以及基于Java的算法实现。包括冒泡排序，选择排序，插入排序，快速排序，堆排序，希尔排序，归并排序，计数排序，桶排序，基数排序。以及冒泡排序最佳时间复杂度为O(n)和快排最坏时间复杂度为O(n^2)的情况。
冒泡排序
基本思想
冒泡排序通过相邻的元素之间的互相比较，将最小的元素“冒泡”到数组最前面。例如4,1,5,9,3,2，首先2跟3比较，变成4,1,5,9,2,3，再2跟9比较并交换，变成4,1,5,2,9,3，再2跟5比较交换，变成4,1,2,5,9,3，再2跟1比较不需要交换，最后1跟4比较并交换，因此进行一次冒泡后的数组变成1,4,2,5,9,3。
算法实现
void bubbleSort(int[] arr) {
if (!checkArray(arr))
return;
for (int i = 0, length = arr.length; i < length; i++) {
for (int j = length - 1; j > i; j--) {
//交换
if (arr[j - 1] > arr[j]) {
arr[j] = (arr[j] + arr[j - 1]) - (arr[j - 1] = arr[j]);
}
}
}
}
算法时间复杂度&稳定性
冒泡排序时间复杂度为O(n^2)，稳定
选择排序
基本思想
选择排序选择出最小的一个元素，与当前数组第一个元素交换即可。例如4,1,5,9,3,2，首先确定当前数组第一个元素位置为0（元素值为4），再从0开始循环找出最小元素，与4交换即可，进行一次选择排序后数组变为1,4,5,9,3,2。
算法实现
void selectSort(int[] arr) {
if (!checkArray(arr))
return;
for (int i = 0, length = arr.length; i < length; i++) {
int min = arr[i];
int minIndex = i;
//选择剩下中的最小的
for (int j = i + 1; j < length; j++) {
if (min > arr[j]) {
min = arr[j];
minIndex = j;
}
}
//如果不是第一个则交换
if (minIndex != i)
arr[minIndex] = (arr[minIndex] + arr[i]) - (arr[i] = arr[minIndex]);
}
}
算法时间复杂度&稳定性
选择排序时间复杂度为O(n^2)，不稳定（例如4(1),5,4(2),3,2，进行一次排序后变为2,5,4(2),3,4(1)）
插入排序
基本思想
插入排序就好比打扑克的时候拿到一张新牌，你要做的就是将新牌插入到已有牌的指定位置。因此我们假设数组第一个元素是有序的（只有一个元素原本也是有序的），再比较之后的数，找到指定的位置插入进去即可。例如4,1,5,9,3,2，进行一次插入排序后就是1,4,5,9,3,2。
算法实现
void insertSort(int[] arr) {
if (!checkArray(arr))
return;
for (int i = 1, length = arr.length; i < length; i++) {
int target = arr[i];//待插入的值
int j = i - 1;
//比待插入的值大则一直后移
for (; j >= 0 && arr[j] > target; j--) {
arr[j + 1] = arr[j];
}
//插入
arr[j + 1] = target;
}
}
算法时间复杂度&稳定性
插入排序时间复杂度为O(n^2)，稳定
快速排序
基本思想
快速排序以一个数为基准（一般选第一个），将比基准数小的全部移到左边，比基准数大的全部移到右边，并且是直接交换小数和大数。例如4,1,5,9,3,2，进行一次快速排序后就是3,1,2,4,9,5。（按照下面的算法算出的结果，不同的算法得出的结果可能不一样）
算法实现
void quickSort(int[] arr) {
if (!checkArray(arr))
return;
quickSort(arr, 0, arr.length - 1);
}
void quickSort(int[] arr, int low, int high) {
if (low >= high)
return;
int left = low;
int right = high;
int value = arr[low];
int valueIndex = low;
while (high > low) {
//必须要>=，否则左右两边的值都是value，则会进入死循环
while (high > low && arr[high] >= value)
high--;
while (high > low && arr[low] <= value)
low++;
arr[low] = (arr[low] + arr[high]) - (arr[high] = arr[low]);
}
//交换基准数，因为基准数在最左边，所以与基准数交换的数要比基准数小，所以先找高位，让高位与低位相遇，这样就能保证相遇时的值肯定比基准数小
arr[valueIndex] = (arr[valueIndex] + arr[high]) - (arr[high] = arr[valueIndex]);
quickSort(arr, left, high - 1);
quickSort(arr, high + 1, right);
}
算法时间复杂度&稳定性
快速排序时间复杂度为O(nlogn)，不稳定（例如9,10(1),7,10(2),3,50，进行一次快排后变为7,3,9,10(2),10(1),50）
堆排序
基本思想
堆排序就是利用堆（完全二叉树）来实现排序。如果是想升序排列就用大顶堆（最大堆，根节点最大，父节点大于等于子节点），如果想降序就用小顶堆（最小堆，根节点最小，父节点小于等于子节点），因为最后堆排序需要将堆顶的元素交换到数组的最后。
堆排序分为2个步骤：
1. 首选，要建立最大堆（最小堆）
2. 接着，交换堆顶（即数组索引为0）与数组最后的元素，交换结束重新排序堆，直到全部交换完毕
算法实现
void heapSort (int[] arr) {
if (!checkArray(arr))
return;
heapBuild(arr);
for (int i = arr.length - 1; i > 0; i--) {
//交换堆顶与i（即当前数组的最后一个）
arr[i] = arr[i] + arr[0] - (arr[0] = arr[i]);
//重新构建有序堆
heapAdjust(arr, 0, i);
}
}
//构建最大堆
void heapBuild (int[] arr){
//因为是完全二叉树，只要从数组的一半开始依次建立有序堆即可
for (int length = arr.length, i = length / 2; i >= 0; i--) {
heapAdjust(arr, i, length);
}
}
//使得index以后的所有节点都是最大堆
void heapAdjust(int[] arr, int index, int length) {
int left = 2 * index + 1;
int right = left + 1;
int largest = index;
if (left < length && arr[left] > arr[largest])
largest = left;
if (right < length && arr[right] > arr[largest])
largest = right;
if (largest != index) {
arr[largest] = arr[largest] + arr[index] - (arr[index] = arr[largest]);
//如果有了交换，则保证以交换的那个节点为根节点的堆依然是最大堆
heapAdjust(arr, largest, length);
}
}
算法时间复杂度&稳定性
堆排序时间复杂度为O(nlogn)，不稳定（例如50,10(1),9,10(2),2，排序后变成2,9,10(2),10(1),50
希尔排序
基本思想
希尔排序是插入排序的一种高效率的实现，也叫缩小增量排序。插入排序如果待排序列是正序的，那么时间复杂度就是O(N)，如果序列是基本有序的，那么插入排序的效率就非常高（减少了数据项移动的操作）。希尔排序就是从一个增量开始，而不是1，进行跳跃式的前移，这样一直循环到1时数组基本就有序了，因此效率会提高很多。
算法实现
void shellSort(int[] arr) {
if (!checkArray(arr))
return;
int d = arr.length / 2;
while (d >= 1) {
for (int i = d, length = arr.length; i < length; i ++) {
int target = arr[i];
int j = i - d;
for (; j >= 0 && arr[j] > target; j -= d) {
arr[j + d] = arr[j];
}
arr[j + d] = target;
}
d /= 2;
}
}
算法时间复杂度&稳定性
希尔排序的分析是复杂的，时间复杂度是所取增量的函数，这涉及一些数学上的难题。但是在大量实验的基础上推出当n在某个范围内时，时间复杂度可以达到O(n^1.3)。不稳定的（这个跟你取的初始步长有关，例子不举了）。使用希尔增量（N/2，N/4…）最坏情况是O(N^2)，因为这些增量未必是互素的，一些较小的增量可能影响很小，而使用Hibbard增量（1,3,7,…2^k-1）则最坏情况是O(N^3/2)（这些证明网上都有，在《Data Structures and Algorithm Analysis in Java》第7章中也有证明），一些更好的增量可以进一步提高算法质量。
归并排序
基本思想
归并排序采用了递归分治的思想，将一个数组分成2半，再2半，再2半，递归排序，最后再合并结果。
算法实现
void mergeSort(int[] arr) {
if (!checkArray(arr))
return;
mSort(arr, 0, arr.length - 1);
}
//采用递归分治的思想，将数组不停的分成两半，直到数组中只有一个元素，再合并
void mSort(int[] arr, int low, int high) {
if (low >= high)
return;
int mid = (high + low) / 2;
mSort(arr, low, mid);
mSort(arr, mid + 1, high);
mMerge(arr, low, mid, high);
}
//将两个有序的数组合并
void mMerge(int[] arr, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int left = low;
int midTmp = mid + 1;
int index = 0;
while (left <= mid && midTmp <= high) {
if (arr[left] <= arr[midTmp])
temp[index++] = arr[left++];
else
temp[index++] = arr[midTmp++];
}
while (left <= mid) {
temp[index++] = arr[left++];
}
while (midTmp <= high) {
temp[index++] = arr[midTmp++];
}
for (int i = 0, size = temp.length; i < size; i++) {
arr[low + i] = temp[i];
}
}
算法时间复杂度&稳定性
归并排序时间复杂度为O(nlogn)，稳定
计数排序
基本思想
计数排序只适合非负整数的排序，思路很简单，就是首先得到这一组数中的最大值，作为数组的上限，再计算各个数的值放在数组对应的下标处，如果多个则++，再计算计数和，即得到在arr中小于等于i的值一共有多少个，排序是只要根据对应值所对应的计数和放在临时数组的指定位置即可。
算法实现
void countSort(int[] arr) {
if (!checkArray(arr))
return;
int max = getMax(arr);
//记录arr对应值的个数（默认值都是0）
int[] countArr = new int[max + 1];
//存入值的临时数组
int[] outArr = new int[arr.length];
//arr中的值作为下标，记录每个值的个数
for (int value : arr)
countArr[value]++;
//将countArr中记录的值改变为累加值，记录在arr中小于等于i的值一共有多少个
for (int i = 1, size = countArr.length; i < size; i++)
countArr[i] += countArr[i - 1];
//将arr中的值根据个数放入到ourArr中的对应位置
for (int value : arr) {
outArr[--countArr[value]] = value;
}
for (int i =0, size = arr.length; i < size; i++)
arr[i] = outArr[i];
}
int getMax(int[] arr) {
int max = 0;
for (int i : arr) {
if (i > max)
max = i;
}
return max;
}
算法时间复杂度&稳定性
计数排序时间复杂度为O(n)。稳定性根据你**将arr中的值根据个数放入到ourArr中的对应位置**采用的方式，如果是倒序arr，则稳定，如果想上述代码中采用的正序arr，则不稳定（顺序正好相反），但是一般是作为稳定的排序算法。
桶排序
基本思想
桶排序提供了一个映射函数，将需要排序的数组中的所有元素映射到数量有限的桶里（应设函数保证如果t1>t2，则f(t1)>f(t2)），如果两个元素映射到同一个桶里，则将他链接起来，再对桶内进行排序，这样就得到了一个有序的排列，再从桶里依次将元素拿出来即可。
算法实现
//映射函数
int f(int x) {
return x / 10;
}
void bucketSort(int[] arr) {
if (!checkArray(arr))
return;
int max = arr[0], min = arr[0];
for (int value : arr) {
if (max < value)
max = value;
if (min > value)
min = value;
}
//桶数
int bucketNum = max / 10 - min / 10 + 1;
//初始化桶
List<List<Integer>> buckets = new ArrayList<>();
for (int i = 0; i < bucketNum; i++) {
buckets.add(new LinkedList<>());
}
//加数组中的数据加入桶中
for (int value : arr) {
buckets.get(f(value)).add(value);
}
//桶内排序
for (int i = 0; i < bucketNum; i++) {
Collections.sort(buckets.get(i));
}
int index = 0;
for (int i = 0; i < bucketNum; i++) {
if (buckets.get(i).size() > 0)
for (int j : buckets.get(i))
arr[index++] = j;
}
}
算法时间复杂度&稳定性
桶排序分为两个部分，一个是将数组中的元素都映射到对应的桶里，这里的复杂度为O(N)，第二部分是将桶里的元素进行排序，这里如果是基于一般的比较排序算法，则最快的时间复杂度为O(nlogn)，因此如果要降低桶排序的时间复杂度，则要尽量将元素映射到不同的桶里。当然，如果要做到这点，那么桶的数量可能就会非常巨大，造成空间浪费，这就是空间和时间之间的权衡问题。
对于N个待排数据，M个桶，平均每个桶[N/M]个数据的桶排序平均时间复杂度为：
O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)
因此桶排序的平均时间复杂度为O(N+C)，其中C=N*(logN-logM)，当N=M时，即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。
桶排序被认为是稳定的。（桶内排序采用稳定的排序算法）
基数排序
基本思想
基数排序也是一种非比较型整数排序算法，它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零（算法层面就是n/radix%10）。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
举个例子：
算法实现
//获得最大元素的位数
int maxBit(int[] arr) {
int size = arr.length;
int max = arr[0];
for (int value : arr) {
if (max < value)
max = value;
}
int num = 1;
while (max >= 10) {
max /= 10;
num++;
}
return num;
}
void radixSort(int[] arr) {
if (!checkArray(arr))
return;
int maxBit = maxBit(arr);
//记录临时数组
int[] tmp = new int[arr.length];
//记录每个尾数对应的个数
int[] count = new int[10];
//记录比较第几位(n/radix%10)
int radix = 1;
for (int i = 0; i < maxBit; i++) {
//重置计数器数组
Arrays.fill(count, 0);
//这里用的思想其实是对每一位进行计数排序
//记录每种尾数的个数
for (int value : arr) {
count[value / radix % 10]++;
}
//计数和
for (int j = 1; j < 10; j++) {
count[j] += count[j - 1];
}
//根据计数和将数据放入到临时数组中
for (int j = arr.length - 1; j >= 0; j--) {
int k = arr[j] / radix % 10;
tmp[--count[k]] = arr[j];
}
for (int j = 0, size = arr.length; j < size; j++) {
arr[j] = tmp[j];
}
//排序高一位
radix *= 10;
}
}
算法时间复杂度&稳定性
基数排序时间复杂度为O(kn)（k为最大元素的位数），稳定
各种排序算法的比较总结
对于冒泡排序最佳为O(n):
public void bubbleSort(int arr[]) {
boolean didSwap;
for(int i = 0, len = arr.length; i < len - 1; i++) {
didSwap = false;
for(int j = 0; j < len - i - 1; j++) {
if(arr[j + 1] < arr[j]) {
swap(arr, j, j + 1);
didSwap = true;
}
}
if(didSwap == false)
return;
}
}
对于快排最坏为O(n^2):
基准数总是最小元素，这样每次只会划分为一个比原数组少1个的子序列以及一个空序列，这样执行的次数为求和(n-i)，i从1到n-1（递归n-1次）。
相关文章