排序算法总结（JAVA版）
2017-07-30 本文已影响301人
AlexanderJLiu
简介：本文主要总结了以下几个排序算法：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序
冒泡排序（Bubble Sort）
基本版原理：从左至右依次进行两两比较，将最大的元素冒泡至最右边，此为1轮冒泡，然后重复n次，n为数组长度。
优化版原理：在基本版里，如果数组已经排好序，时间复杂度并不是最优的O(n)，为了使得复杂度降低，优化版记录数组中最后一次交换的位置，则此位置后的数组已经有序，则每次只需遍历到该位置即可。
冒泡排序是稳定的排序
1. Java源码实现：
public class BubbleSort {
/**
* 基本版的冒泡排序
* @param nums
*/
public void buubleSort(int[] nums) {
int len = nums.length;
if (len <= 1) return ;
for (int i=0; i<len; i++) {
for (int j=0; j<len-i-1; j++) {
if (nums[j] > nums[j+1]) {
swap(nums, j, j+1);
}
}
}
}
/**
* 优化版的冒泡排序
* @param nums
*/
public void bubbleSortOptimize(int[] nums) {
int len = nums.length;
if (len <= 1) return ;
int lastSwapPos = len - 1;//最后一次交换的位置
while (lastSwapPos != 0) {//为0时循环终止，排序完成
int pos = 0;
for (int i=0; i<lastSwapPos; i++) {
if (nums[i] > nums[i+1]) {
swap(nums, i, i+1);
pos = i;//每发生一次交换，则记录交换的位置
}
}
lastSwapPos = pos;//更新最后一次交换的位置
}
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
2. 冒泡排序动态排序图：
bubble sort
选择排序 （Selection Sort）
原理：从左至右选出最大的元素，并与最右边未排好序的第一个元素进行交换，此为1次选择排序，然后重复n次，n为数组长度。
选择排序是不稳定的排序
1. Java源码实现：
public class SelectionSort {
/**
* 选择排序
* @param nums
*/
public void selectionSort(int[] nums) {
int len = nums.length;
if (len <= 1) return;
for (int i=0; i<len; i++) {
int index = 0;//最大元素索引
for (int j=1; j<len-i; j++) {
if (nums[j] > nums[index]) index = j;
}
swap(nums, index, len-i-1);//元素交换
}
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
2. 选择排序动态排序图：
selection sort
插入排序 （Insertion Sort）
原理：遍历数组中的每个元素，对于每个元素，其左边的元素已经排好序，只需将其插入到对应的位置即可，即从右至左遍历左边的元素，并与比该元素大的进行位置交换。
插入排序是稳定的排序
1. Java源码实现：
public class InsertionSort {
/**
* 插入排序
* @param nums
*/
public void insertionSort(int[] nums) {
int len = nums.length;
if (len <= 1) return;
for (int i=0; i<len; i++) {
for (int j=i; j>0; j--) {
if (nums[j] < nums[j-1]) swap(nums, j, j-1);
}
}
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
2. 插入排序动态排序图：
insertion sort
希尔排序（Shell Sort）
原理：希尔排序是插入排序的一种更高效的改进版本。首先根据设定的步长gap，它将待排序的数组分为若干个子序列，然后分别对每个子序列进行插入排序，修改步长，重复上面的操作直至步长为1，排序完成。
希尔排序是不稳定的排序
1. Java源码实现：
public class ShellSort {
/**
* 希尔排序O(n^3/2)
* @param nums
*/
public void shellSort(int[] nums) {
int len = nums.length;
if (len <= 1) return;
int gap = 1;
//设置步长
while (gap < len / 3) {
gap = gap * 3 + 1;
}
//根据步长循环
for (; gap > 0; gap /= 3) {
//对gap位置后的元素进行简单插入排序
for (int i = gap; i < len; i++) {
int j = i - gap, tmp = nums[i];
for (; j >= 0 && nums[j] > tmp; j -= gap) {
//将大于tmp的元素后移gap个单位
nums[j + gap] = nums[j];
}
//放置tmp元素
nums[j + gap] = tmp;
}
}
}
}
2. 希尔排序演示图：
shell sort
归并排序 （Merge Sort）
递归版原理：将待排序长度为n的数组分为两个长度为n/2的子序列，然后对这两个子序列分别进行归并排序，最后将排好序的两个子序列进行合并成排好序的数组。由于子序列的合并不能在原数组直接进行，所以需要长度为n的辅助存储空间在子序列合并时使用。
迭代版原理：根据归并排序的思想，先将原数组分为不可再分的子序列，然后再逐层合并。所以迭代版归并排序中首先设定一个步长block为1，并在循环的过程中每次增加1倍，目的是将原数组分为n/block个子序列，每个序列的长度为block，然后针对每个block，对每两个相邻的长度为block的序列进行排序。当block大于等于n/2，排序完成。
归并排序是稳定的排序
1. Java源码实现：
public class MergeSort {
/**
* 递归版归并排序
* @param nums
* @param start 起始位置
* @param end 结束位置
* @param extra 辅助的存储空间
*/
public void mergeSort(int[] nums, int start, int end, int[] extra) {
int len = nums.length;
if (len <= 1 || start >= end) return;
int middle = (start + end)/2;
//子序列1从start-middle
mergeSort(nums, start, middle, extra);
//子序列2从middle+1-end
mergeSort(nums, middle+1, end, extra);
//子序列1和2进行合并
merge(nums, start, middle, end, extra);
}
/**
* 子序列合并操作
* @param nums
* @param start-middle 子序列1
* @param middle+1-end 子序列2
* @param extra
*/
public void merge(int[] nums, int start, int middle, int end, int[] extra) {
int left = start, right = middle+1;
int index = start;
//将两个子序列的元素值进行比较，从小到大拷贝进辅助数组
while (left <= middle && right <= end) {
if (nums[left] < nums[right]) {
extra[index++] = nums[left++];
} else {
extra[index++] = nums[right++];
}
}
//如果两个子序列的任一个还有元素未拷贝，则继续拷贝
while (left <= middle) extra[index++] = nums[left++];
while (right <= end) extra[index++] = nums[right++];
//将合并后的元素重新拷贝回原数组
for (int i=start; i<=end; i++) {
nums[i] = extra[i];
}
}
/**
* 迭代版归并排序
* @param nums
* @param extra 辅助的存储空间
*/
public void mergeSortIterator(int[] nums, int[] extra) {
int len = nums.length;
if (len <= 1) return;
//步长block
for (int block=1; block<len; block=block*2) {
//每两个相邻的长度为block的序列进行排序
for (int start=0; start<len; start=start+block*2) {
int left = start,
middle = (start + block) < len ? (start + block) : len,
end = (start + block*2) < len? (start + block*2) : len;
int right = middle, index = start;
while (left < middle && right < end) {
if (nums[left] < nums[right]) {
extra[index++] = nums[left++];
} else {
extra[index++] = nums[right++];
}
}
while (left < middle) extra[index++] = nums[left++];
while (right < end) extra[index++] = nums[right++];
for (int i=start; i<end; i++) nums[i] = extra[i];
}
}
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
2. 归并排序动态排序图：
merge sort
快速排序 （Quick Sort）
递归版原理：首先，选取一个元素作为基准pivot，将小于该基准的元素放在左边，大于该基准的元素放在右边，该基准位于中间位置，称为分区（partition）操作，然后递归地分别对左右两边的元素进行快速排序。根据所选基准元素位置的不同，源码中分别实现了选取第一个元素、最后一个元素及中间元素作为基准的递归快速排序，原理相同，但实现上略有不同，需要注意。
迭代版原理：借助栈来对待排序序列的起始位置和结束位置进行保存，首先入栈全局数组的位置即0-n-1，然后循环访问该栈，只要栈非空，则继续排序，并将新的位置信息入栈，直至栈空，排序完成。
快速排序是不稳定的排序
1. Java源码实现：
import java.util.LinkedList;
public class QuickSort {
/**
* 选择第一个元素作为基准的递归快排
* @param nums
* @param start 起始位置
* @param end 结束位置
*/
public void quickSortStart(int[] nums, int start, int end) {
int len = nums.length;
if (len <= 1 || start >= end) return;
int left = start, right = end;
int pivot = nums[left];
/*每次循环先从右至左遍历，找到比基准元素小的第一个元素，
* 然后从左至右遍历，找到比基准元素大的第一个元素，
* 最后交换两个元素的位置，循环终止时left==right，
* 且right指向最后一个小于该基准元素的位置
*/
while (left < right) {
while (left < right && nums[right] >= pivot) right --;
while (left < right && nums[left] <= pivot) left ++;
swap(nums, left, right); //when left == right;
}
//交换基准元素与最后一个小于基准的元素的位置
swap(nums, start, right);
quickSortStart(nums, start, right-1);
quickSortStart(nums, right+1, end);
}
/**
* 选择最后一个元素作为基准的递归快排
* @param nums
* @param start 起始位置
* @param end 结束位置
*/
public void quickSortEnd(int[] nums, int start, int end) {
int len = nums.length;
if (len <= 1 || start >= end) return;
int left = start, right = end;
int pivot = nums[end];
/*每次循环先从左至右遍历，找到比基准元素大的第一个元素，
* 然后从右至左遍历，找到比基准元素小的第一个元素，
* 最后交换两个元素的位置，循环终止时left==right，
* 且left指向第一个大于该基准元素的位置
*/
while (left < right) {
while (left < right && nums[left] <= pivot) left ++;
while (left < right && nums[right] >= pivot) right --;
swap(nums, left, right);
}
//交换基准元素与第一个大于基准的元素的位置
swap(nums, left, end);
quickSortEnd(nums, start, left-1);
quickSortEnd(nums, left+1, end);
}
/**
* 选择中间位置元素作为基准的递归快排
* @param nums
* @param start 起始位置
* @param end 结束位置
*/
public void quickSortMiddle(int[] nums, int start, int end) {
int len = nums.length;
if (len <= 1 || start >= end) return;
int left = start, right = end;
int middle = (left + right)/2;
int pivot = nums[middle];
//注意与以上两种方法的不同 left <= right 而非<
while (left <= right) {
//nums[left] < pivot 而非 <= , nums[right] > pivot 而非>=
while (left <= right && nums[left] < pivot) left ++;
while (left <= right && nums[right] > pivot) right --;
//需要判断因为left可能大于right
if (left <= right){
swap(nums, left, right);
//需要有，因为遇到等于pivot的元素时会陷入死循环
left++;
right--;
}
}
quickSortMiddle(nums, start, right);
quickSortMiddle(nums, left, end);
}
class Element {
int start, end;
public Element(int start, int end) {
this.start = start;
this.end = end;
}
}
/**
* 迭代版快排
* @param nums
*/
public void quickSortIterator(int[] nums) {
int len = nums.length;
if (len <= 1) return;
LinkedList<Element> s = new LinkedList<Element>();
s.push(new Element(0, len-1));
while (!s.isEmpty()) {
Element e = s.pop();
int start = e.start, end = e.end;
int left = start, right = end;
if (left >= right) continue;
int pivot = nums[left];
while (left < right) {
while (left < right && nums[right] >= pivot) right--;
while (left < right && nums[left] <= pivot) left++;
swap(nums, left, right);
}
swap(nums, start, right);
s.push(new Element(start, right - 1));
s.push(new Element(right + 1, end));
}
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
2. 快速排序动态排序图：
quick sort
堆排序 （Heap Sort）
原理：首先将待排序数组构建为大小为n的最大（小）堆，然后将最大的堆顶元素与数组最后一个元素交换，将最大的元素放在最后一个位置，接下来不断调整最大堆并进行与上面相同的操作，此时堆的大小为n-1并依次递减，直至为0时，排序完成。
堆排序是不稳定的排序
1. Java源码实现：
public class HeapSort {
/**
* 最大堆排序
* @param nums
*/
public void heapSortMax(int[] nums) {
int len = nums.length;
//建堆操作
for (int i=(len-1)/2; i>=0; i--) {
maxHeap(nums, i, len);
}
//排序操作
for (int i=0; i<len; i++) {
swap(nums, 0, len-i-1);
maxHeap(nums, 0, len-i-1);
}
}
/**
* 最大堆调整操作
* @param nums
* @param parent 父节点
* @param len 堆的大小
*/
public void maxHeap(int[] nums, int parent, int len) {
int left = parent * 2 + 1;
if (left > len-1) return;
int right = left + 1;
int max = left;
if (right <= len-1 && nums[left] < nums[right]) max = right;
if (nums[parent] < nums[max]) {
swap(nums, parent, max);
maxHeap(nums, max, len);
}
}
/**
* 最小堆排序
* @param nums
*/
public void heapSortMin(int[] nums) {
int len = nums.length;
if (len <= 1) return;
//建堆操作
for (int i=(len-1)/2; i>=0; i--){
minHeap(nums, i, len);
}
//排序操作
for (int i=0; i<len; i++) {
swap(nums, 0, len-1-i);
minHeap(nums, 0, len-1-i);
}
}
/**
* 最小堆调整操作
* @param nums
* @param parent 父节点
* @param len 堆的大小
*/
public void minHeap(int[] nums, int parent, int len) {
int left = parent * 2 + 1;
if (left > len-1) return;
int right = left + 1;
int min = left;
if (right <= len-1 && nums[right] < nums[left]) min = right;
if (nums[parent] > nums[min]) {
swap(nums, parent, min);
minHeap(nums, min, len);
}
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
2. 堆排序动态排序图：
heap sort
计数排序 （Counting Sort）
原理：找出待排序数组中最小和最大的元素，统计每个元素i出现的次数并存入数组count的第i-min项，然后累加所有的计数（count数组中的第一个元素开始，每一项和前一项相加并存入该项），能够得出每个元素的最终位置，最后考虑算法的稳定性，反向填充目标数组（倒序遍历原数组），将每个元素nums[i]放入新数组extra中第count[i]项，每放入一个元素就将count[i]减1，详见稳定版计数排序。当不考虑稳定性时，可以省略辅助数组extra，遍历数组count，按顺序将i放回原数组，详见优化版计数排序。
计数排序是稳定的排序
1. Java源码实现：
public class CountingSort {
/**
* 稳定版计数排序
* @param nums
* @return int[]
*/
public int[] countingSort(int[] nums) {
int len = nums.length;
if (len <= 1) return nums;
int[] extra = new int[len];
int min = nums[0], max = nums[0];
for (int i = 1; i < len; i++) {
min = Math.min(min, nums[i]);
max = Math.max(max, nums[i]);
}
int k = max - min + 1;
int[] count = new int[k];
//计数
for (int i = 0; i < len; i++) {
count[nums[i] - min]++;
}
//计数累加
for (int i = 1; i < k; i++) {
count[i] = count[i] + count[i-1];
}
//考虑到排序的稳定性，所以需要进行反向填充
for (int i = len - 1; i >= 0; i--) {
extra[--count[nums[i] - min]] = nums[i];
}
return extra;
}
/**
* 优化版计数排序
* @param nums
*/
public void countingSortOptimize(int[] nums) {
int len = nums.length;
if (len <= 1) return;
int min = nums[0], max = nums[0];
for (int i = 1; i < len; i++) {
min = Math.min(min, nums[i]);
max = Math.max(max, nums[i]);
}
int k = max - min + 1;
int[] count = new int[k];
//计数
for (int i = 0; i < len; i++) {
count[nums[i] - min]++;
}
int index = 0;
for (int i = 0; i < k; i++) {
while (count[i] != 0) {
nums[index++] = i + min;
count[i]--;
}
}
}
}
2. 计数排序动态排序图：
optimal counting sort
桶排序
原理：先将待排序数组分到有限数量的桶里，每个桶再分别进行排序（排序算法可以是其他排序算法也可以是递归的桶排序）。具体过程如下：设置一定数量的数组作为空桶，然后将待排序的数组中的元素放到对应的桶中，再对每个非空桶进行排序，最后将非空桶的元素依次放回原数组。
桶排序是稳定的排序
1. Java源码实现：
import java.util.ArrayList;
import java.util.List;
public class BucketSort {
/**
* 桶排序
* @param nums
*/
public void bucketSort(int[] nums) {
int len = nums.length;
if (len <= 1) return;
int min = nums[0], max = nums[0];
for (int i = 0; i < len; i++) {
min = Math.min(min, nums[i]);
max = Math.max(max, nums[i]);
}
//步长
int step = 2;
//桶的个数
int bucketNum = max/step - min/step + 1;
List<List<Integer>> buckets = new ArrayList<List<Integer>>();
//桶的初始化
for (int i = 0; i < bucketNum; i++) {
buckets.add(new ArrayList<Integer>());
}
//将待排序数组元素装桶
for (int i = 0; i < len; i++) {
int index = (nums[i] - min)/step;
buckets.get(index).add(nums[i]);
}
//将桶内元素进行插入排序后重新放回原数组
int index = 0;
for (int i = 0; i < bucketNum; i++) {
List<Integer> bucket = buckets.get(i);
insertionSort(bucket);
for (int j : bucket) {
nums[index++] = j;
}
}
}
/**
* 桶内元素的插入排序
* @param bucket
*/
public void insertionSort(List<Integer> bucket) {
int size = bucket.size();
for (int i = 0; i < size; i++) {
for (int j = i; j > 0; j--) {
if (bucket.get(j) < bucket.get(j - 1)) {
swap(bucket, j, j - 1);
}
}
}
}
public void swap(List<Integer> bucket, int i, int j) {
int tmp = bucket.get(i);
bucket.set(i, bucket.get(j));
bucket.set(j, tmp);
}
}
2. 桶排序演示图：
bucket sort（step=20）
基数排序
原理：将整数按位切割成不同的数字，然后按每个位数分别比较。具体过程如下：先找出待排序数组的最大数，并计算其位数，即最终循环排序的次数，然后按照位数从最低位开始进行计数排序，直到最高位，最后数组排序完成。
基数排序是稳定的排序
1. Java源码实现：
public class RadixSort {
/**
* 基数排序（LSD：Least Significant Digital）
* @param nums
*/
public void radixSort(int[] nums) {
int len = nums.length;
if (len <= 1) return;
int digital = maxDigital(nums, len);
//需要循环排序的次数，为最大数的位数
for (int i = 0; i < digital; i++) {
int[] count = new int[10];
//每次计算的基数
int radix = (int)Math.pow(10, i);
//计数
for (int j = 0; j < len; j++) {
count[(nums[j] / radix) % 10]++;
}
//累加
for (int j = 1; j < 10; j++) {
count[j] = count[j] + count[j-1];
}
//反向填充
int[] tmp = new int[len];
for (int j = len - 1; j >= 0; j--) {
tmp[--count[(nums[j] / radix) % 10]] = nums[j];
}
//重新赋值给原数组
for (int j = 0; j < len; j++) {
nums[j] = tmp[j];
}
}
}
/**
* 求最大数的位数
* @param nums 待排序数组
* @param len 数组长度
* @return 位数
*/
public int maxDigital(int[] nums, int len) {
int max = nums[0];
for (int i = 1; i < len; i++) {
max = Math.max(max, nums[i]);
}
int digital = 1;
while (max >= 10) {
max = max / 10;
digital++;
}
return digital;
}
}
2. 基数排序动态排序图：
radix sort（LSD）
