排序算法总结 博客分类： java 算法排序Java数据结构快速排序
排序算法几种分类方式：
1，稳定排序和不稳定排序
如果a==b， 当排序之前a在b的前面，排序后，a仍然在b的前面，则该排序算法为稳定排序算法。否则为不稳定排序算法。
2，非线性时间比较类排序和线性时间非比较类排序算法
非线性时间比较类排序：通过比较来决定元素间的相对位置，由于比较次数，使其时间复杂度不能
突破O(nlogn)。
线性时间非比较类排序：不通过比较来决定元素间的相对位置，它可以突破比较排序的时间下限，以线性时间运行。
几种常见的排序算法介绍：
1，选择排序
算法原理：依次在元素间比较，从集合中找出最小的元素，放到集合最前面，再从剩下的集合中找出次小的元素，再放到当前集合最前面；依次循环，把所有的元素排好序。
平均时间复杂度O(n*n)，空间复杂度O(1)。
选择排序是不稳定排序。
// 选择排序：
public int[] selectSort(int[] nums) {
long start = System.currentTimeMillis();
for (int i = 0; i < nums.length; i++) {
int minIndex = i;
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
swap(nums, i, minIndex);
}
System.out.println("Select Sort, count time = " + (System.currentTimeMillis() - start) + "ms");
return nums;
}
private void swap(int[] nums, int x, int y) {
if (x == y)
return;
int temp = nums[x];
nums[x] = nums[y];
nums[y] = temp;
}
2，快速排序
算法原理：从元素集合中挑选出一个基准(Pivot)，一次遍历之后，把所有大于基准的元素放在基准值的右边，所有小于基准的元素放在基准值的左边。然后递归分别对左边和右边执行同样的操作。
遍历过程如下：首先选定基准，然后分别从左边和右边开始遍历，直至左右相遇则遍历完成。左边开始往右边遍历时，遇到比基准值大的元素，则停下来，右边开始往左边遍历时，遇到比基准值小的元素，则停下来，然后把左右两个元素交换。然后继续遍历，直至相遇。
注意：如果选定的基准是左边第一个元素，则先从右边开始往左遍历，这样能保证停下来时的元素是不大于基准的元素。反之，则从左边开始遍历。
平均时间复杂度O(nlogn)，空间复杂度O(logn)。
快速排序是不稳定排序
// 快速排序：
public int[] quickSort(int[] nums) {
long start = System.currentTimeMillis();
if (nums == null || nums.length == 0)
return nums;
quickSortByPivot(nums, 0, nums.length - 1);
System.out.println("Quick Sort, count time = " + (System.currentTimeMillis() - start) + "ms");
return nums;
}
private void quickSortByPivot(int[] nums, int left, int right) {
int l = left, r = right;
int pivot = nums[left];
while (l < r) {
while (r > l && nums[r] >= pivot)
r--;
while (r > l && nums[l] <= pivot)
l++;
if (l < r)
swap(nums, l, r);
}
swap(nums, left, l);
if (l - 1 > left)
quickSortByPivot(nums, left, l - 1);
if (right > l + 1)
quickSortByPivot(nums, l + 1, right);
}
3，简单插入排序
算法原理：把当前元素插入到已排好序的元素集合的对应位置。把第一个元素当成已经排好序的元素，从第二个元素(新元素)开始，从排好序的元素(待比较元素)中后向前逐一扫描比较，如果待比较的元素比新元素大，则把新元素与待比较元素交换，然后新元素继续往前比较，直至结束。当每个元素都与排好序的元素完成比较，则排序完成。
平均时间复杂度O(n*n)，空间复杂度O(1)。
简单插入排序是稳定排序
// 简单插入排序：
public int[] simpleInsertSort(int[] nums) {
long start = System.currentTimeMillis();
for (int i = 1; i < nums.length; i++) {
int pre = i - 1, cur = i;
while (pre >= 0 && nums[pre] > nums[cur]) {
swap(nums, pre, cur);
cur = pre;
pre--;
}
}
System.out.println("Simple Insert Sort,count time = " + (System.currentTimeMillis() - start) + "ms");
return nums;
}
4，希尔(shell)排序(缩小增量排序)
算法原理：是插入排序的改进版，考虑到插入排序时，有可能某个元素需要插入到比较远的位置，导致不断的重复插入。因此希尔排序会优先比较距离较远的元素。希尔排序引入步长概念，先选定一个步长(可根据集合大小确定)，然后使用插入排序思想比较相隔步长距离的各个元素。然后把步长减一，继续比较，直至步长为1，此时相当于插入排序，但是目前的集合已经近似有序了。
平均时间复杂度O(n^1.3)，空间复杂度O(1)。
希尔排序是不稳定排序。
// 希尔排序 ，
public int[] shellSort(int[] nums) {
long start = System.currentTimeMillis();
if (nums == null || nums.length == 0)
return null;
int gap = nums.length / 3;// 步长
while (gap > 0) {
for (int k = 0; k < gap; k++) {
int cur = k;
int pre = k;
while (cur < nums.length) {
if (nums[cur] < nums[pre]) {
swap(nums, cur, pre);
}
pre = cur;
cur += gap;
}
}
gap--;
}
System.out.println("Shell Sort,count time = " + (System.currentTimeMillis() - start) + "ms");
return nums;
}
5，冒泡排序
算法原理：每次遍历一次集合，比较相邻元素，把较大的元素移到后面，完成一次遍历时，则最大的元素已经移到最后，然后继续遍历剩下的无序集合，把当前集合最大的移到最后面。经历n次遍历后，完成排序。
冒泡排序还可以稍微改进，当排序过程中，发现待排序集合已经是有序的，则可以不需要进一步遍历了。
平均时间复杂度O(n*n)，空间复杂度O(1)。
冒泡排序是稳定排序。
// 冒泡排序:
public int[] bubbleSort(int[] nums) {
long start = System.currentTimeMillis();
if (nums == null || nums.length == 0)
return null;
for (int i = 0; i < nums.length; i++) {
boolean isSorted = true;// 假设当前已经有序,冒泡排序改进，如果当前循环发现已经有序，则不需要继续遍历。
for (int j = 1; j < nums.length - i; j++) {
if (nums[j] < nums[j - 1]) {
swap(nums, j, j - 1);// 一次遍历后，如果有交换动作，则不是有序的.
isSorted = false;
}
}
System.out.println("bubble Sort current index:" + i);
if (isSorted)
return nums;
}
System.out.println("Bubble Sort,count time = " + (System.currentTimeMillis() - start) + "ms");
return nums;
}
6，堆排序
算法原理：堆排序是利用堆这种数据结构来设计的排序算法。堆可以看做一个近似完全二叉树的结构。堆分为大顶堆和小顶堆。大顶堆满足如下性质，父节点的值总是大于(等于)子节点的值，小顶堆满足如下性质，父节点的值总是小于(等于)子节点的值。
从0开始对堆中的节点进行编号，则其节点和其父节点以及子节点的编号关系如下，当前节点编号为i:
父节点编号 parent(i) = i / 2;
左子节点编号 left(i) = 2 * i + 1;
右子节点编号 right(i) = 2 * i + 2;
堆排序过程为首先根据集合元素大小建立一个大顶堆，当前的堆是无序的，然后对每个元素进行调整，使其符合大顶堆的规则，当前节点值大于等于子节点值。完成一次堆的调整后，堆的第一个元素，即堆顶元素，则为集合中的最大元素。此时堆顶元素为有序元素，把它与集合中的最后一个位置的元素互换，然后继续为剩下的其他元素创建大顶堆。直至最后，所有的元素都为有序元素。
平均时间复杂度O(nlogn)，空间复杂度O(1)。
堆排序是不稳定排序。
// 最大堆排序：
public int[] heapSort(int[] nums) {
long start = System.currentTimeMillis();
if (nums == null || nums.length == 0)
return null;
buildMaxHeap(nums);
System.out.println("Heap Sort,count time = " + (System.currentTimeMillis() - start) + "ms");
return nums;
}
private void adjustHeapOfIndex(int[] nums, int index, int heapSize) {
// System.out.println("index|heapSize:" + index + "|" + heapSize);
int left = index * 2 + 1;
int right = index * 2 + 2;
int largest = index;
if (left < heapSize && nums[left] > nums[largest])
largest = left;
if (right < heapSize && nums[right] > nums[largest])
largest = right;
if (index != largest) {
swap(nums, index, largest);
adjustHeapOfIndex(nums, largest, heapSize);
}
// this.printArrays("adjust heap", nums);
}
private int[] buildMaxHeap(int[] nums) {
int heapSize = nums.length;
while (heapSize > 0) {// 从nums.length到1，不断构建最大堆；
// 构建最大堆；
for (int i = heapSize - 1; i >= 0; i--) { // 针对每个index,不断调整堆;
adjustHeapOfIndex(nums, i, heapSize);
}
// this.printArrays("build max heap:",nums);
swap(nums, 0, heapSize - 1); // 堆构建完成后 最大的值为nums[0],完后交换放到最后
heapSize--;
}
return nums;
}
7，归并排序
算法原理：归并排序主要是采用分治法，把两个已排好序的子集合合并成一个有序的集合。子集的排序则是采用递归方法，如果子集只包含一个元素，则为一个有序的集合。
平均时间复杂度O(nlogn)，空间复杂度O(n)。
归并排序是稳定排序。
// 归并排序
public int[] mergeSort(int[] nums) {
long start = System.currentTimeMillis();
if (nums == null || nums.length == 0)
return null;
// System.out.println("start to merge sort:");
int[] temp = new int[nums.length];
mergeSort(nums, 0, nums.length - 1, temp);
System.out.println("Merge Sort,count time = " + (System.currentTimeMillis() - start) + "ms");
return nums;
}
public void mergeSort(int[] nums, int start, int end, int[] temp) {
if (end - start > 0) {
int sublength = (end - start) / 2;
mergeSort(nums, start, start + sublength, temp);// 分别把两个子串排好序 即一直划分到只剩一个元素，则就是一个排好序的子串。
mergeSort(nums, start + sublength + 1, end, temp);
// System.out.println("Merge Sort:" + start + "|" + sublength + "|" + end);
mergeArrays(nums, start, start + sublength, start + sublength + 1, end, temp);// 把两个排好序的子串合并
}
}
private int[] mergeArrays(int[] nums, int lstart, int lend, int rstart, int rend, int[] temp) {
if ((lend - lstart) < 0 && (rend - rstart) < 0)
return nums;
int tempindex = lstart;
int leftindex = lstart, rightindex = rstart;
// System.out.println("tempindex|leftindex " + tempindex + "|" + leftindex);
while (leftindex <= lend && rightindex <= rend) {
if (nums[leftindex] <= nums[rightindex]) {
temp[tempindex++] = nums[leftindex++];
} else {
temp[tempindex++] = nums[rightindex++];
}
}
while (leftindex <= lend) {
temp[tempindex++] = nums[leftindex++];
}
while (rightindex <= rend) {
temp[tempindex++] = nums[rightindex++];
}
// System.out.println("fininsh index " + tempindex + "|" + leftindex);
for (int k = lstart; k <= rend; k++) {// 把经过处理的数组里的值全部更新到原数组中
nums[k] = temp[k];
}
// this.printArrays("Merge Arrays:", nums);
return nums;
}
8，基数排序
算法原理：基数排序是把待排序的数字分为低位和高位，低位先排序，然后收集，再按高位排序，再收集，直至最高位，则排序完成。注意基数排序无法处理负数。
排序过程为，首先得到集合中的最大数，根据最大数，得到需要按位循环排序的次数。
在每次按位排序时，先初始化10个桶，分别存放余数为0-9的元素个数，在一次遍历之后，10个桶中已保存各个余数出现的次数，然后再根据余数个数更新10个桶中的相应元素应该存放的位置，比如余数为1的元素会排在余数为0的元素的后面，因此如果余数为0的元素个数为5，则余数为1的元素至少会在第5个位置之后，由此统计元素应该在集合中出现的位置。
之后再次从大到小遍历整个集合，根据元素的余数，得到对应桶的值，即为该元素在新的集合中的下标值，存放好一个元素，就把对应桶中的值相应减一。遍历结束，则这次按位排序结束，得到一个按低位排序的集合。
再取较高位，进行排序。直至按最高位排序结束，则此时得到的集合就是一个有序的集合。
平均时间复杂度O(2n*k)，k为按位排序的次数；空间复杂度O(n+k)，k为桶的数量；数据量大的话，k会远远小于n。
基数排序是稳定排序。
// 基数排序 基数排序不能处理负数；
public int[] radixSort(int[] nums) {
long start = System.currentTimeMillis();
if (nums == null || nums.length == 0)
return null;
int max = nums[0];
for (int cur : nums) {// 先得到最大数
if (cur > max)
max = cur;
}
int[] temp = new int[nums.length];
int exp = 1;
do {
int[] buckets = new int[10];// 针对余数的桶 统计余数个数
for (int j = 0; j < nums.length; j++) {
buckets[(nums[j] / exp) % 10]++;// 保存每个余数出现的个数
}
// this.printArrays("buckets nums of exp:" + exp, buckets);
for (int l = 1; l < 10; l++) {
buckets[l] += buckets[l - 1];// 统计余数对应的数按顺序出现在整个数组中的位置 即余数越小 则其在数组中排在越前面
}
// this.printArrays("buckets:", buckets);
// this.printArrays("before bucket:", nums);
// 从数组最后往前循环 因为buckets中数据的位置从大到小递减.
for (int m = nums.length - 1; m >= 0; m--) {
// System.out.println("m, value:" + m + "|" + nums[m] + "|" +
// buckets[(nums[m]/exp)%10]);
// this.printArrays("nums:", nums);
temp[buckets[(nums[m] / exp) % 10] - 1] = nums[m];// 每存储一个数据后，则把buckets中对应的数据减一；
buckets[(nums[m] / exp) % 10]--;
// this.printArrays("buckets:", buckets);
}
for (int k = 0; k < nums.length; k++) {// 更新值
nums[k] = temp[k];
}
// this.printArrays("After bucket:" + exp, temp);
exp *= 10;
} while (max / exp > 0);
System.out.println("Radix Sort,count time = " + (System.currentTimeMillis() - start) + "ms");
return nums;
}
9，计数排序
算法原理：计数排序不是基于比较，而是将待排序的数据转换为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求待排序的数据必须是有确定范围的整数。
排序过程为，先得到待排序数据中的最大值和最小值，然后根据最大值和最小值开辟一个新的数组空间，然后遍历整个数据集合，统计各个元素出现的次数，并且存入与元素值对应的数组下标。
然后对数组中的计数进行统计，计算出每个元素应该存放的位置，最后反向遍历数据集合，根据每个元素值，在数组中获取元素应该存放的位置。
平均时间复杂度O(n+k)，空间复杂度(n+k)。k为数据集合中最大值和最小值的范围。如果待排序集合数据比较集中，计算排序是一个很有效的排序算法。
计算排序是稳定排序。
// 计数排序
public int[] countingSort(int[] nums) {
long start = System.currentTimeMillis();
if (nums == null || nums.length == 0)
return null;
// 先得到待排序数据的范围
int min = nums[0], max = nums[0];
for (int curvalue : nums) {
if (curvalue < min)
min = curvalue;
if (curvalue > max)
max = curvalue;
}
// 根据数据范围初始化数组 进行计数
int[] counts = new int[max - min + 1];
// 遍历数组 进行计数
for (int k : nums) {
counts[k - min]++;
}
// 更新数组中各元素的位置
for (int k = 1; k < counts.length; k++) {
counts[k] += counts[k - 1];
}
this.printArrays("Counting arr:", counts);
int[] temp = new int[nums.length];
for (int i = nums.length - 1; i >= 0; i--) {
// System.out.println("counts index:" + (nums[i]-min) + ",count value:" +
// counts[nums[i]-min]);
temp[counts[nums[i] - min] - 1] = nums[i];
counts[nums[i] - min]--;
}
for (int j = 0; j < nums.length; j++) {// 更新值
nums[j] = temp[j];
}
System.out.println("Counting Sort,count time = " + (System.currentTimeMillis() - start) + "ms");
return nums;
}
10，桶排序
算法原理：桶排序是计数排序的升级版，利用函数的映射关系，把数据映射到有限的桶中，然后对每个桶进行单独排序，可使用快速排序等其他算法。最后把几个桶的元素合并，完成排序。
桶排序的时间复杂度取决于各个桶的排序算法，其他部分的时间复杂度为O(n)。显然，桶划分得越多，各个桶中的数据越少，每个桶的排序时间越少，效率越高，但相应的，空间消耗也越大。
平均时间复杂度O(n+k)，空间复杂度O(n+k)。
// 桶排序算法
public int[] bucketSort(int[] nums) {
long start = System.currentTimeMillis();
if (nums == null || nums.length == 0)
return null;
if (nums.length <= 1)
return nums;
//this.printArrays("bucket sort:", nums);
// 先得到待排序数据的范围
int min = nums[0], max = nums[0];
for (int curvalue : nums) {
if (curvalue < min)
min = curvalue;
if (curvalue > max)
max = curvalue;
}
// 根据数的范围 确定桶的个数 以及桶的映射函数
// 在此假设最多分十个桶 然后把数据分别放入对应桶内
// 每个桶使用List
int bucketNum = 10;
int step = 0;
if ((max - min) < 10)
bucketNum = max - min + 1;
step = (max - min + 1) / bucketNum;// 根据bucketNum和step分出bucketNum个桶，范围 [min,min+step)，最后一个桶还包含剩下的余数;
// 初始化桶
List[] buckets = new ArrayList[bucketNum];
for (int bk = 0; bk < buckets.length; bk++) {
buckets[bk] = new ArrayList();
}
System.out.println("Bucketnum:" + bucketNum);
// 遍历数组 把元素分别放入桶中
for (int curnum : nums) {
int curindex = (curnum - min) / step;
if (curindex > buckets.length - 1)
curindex = buckets.length - 1;
System.out.println("curnum:" + curnum + ",curindex = " + curindex + ",min = " + min + ",step = " + step);
buckets[curindex].add(curnum);
}
// 分别对各个桶进行排序 并且把每个桶中各元素合并
int index = 0;
for (List list : buckets) {
int[] temp = new int[list.size()];
for (int k = 0; k < list.size(); k++) {
temp[k] = (Integer) list.get(k);
}
int[] tempresult = bucketSort(temp);
if (tempresult != null)
for (int value : tempresult)
nums[index++] = value;
}
System.out.println("Bucket Sort,count time = " + (System.currentTimeMillis() - start) + "ms");
return nums;
}
排序算法总结：
1，如果待排序的集合规模较小，如n<50，可用简单插入排序或者选择排序。
2，如果待排序的集合基本有序，可用简单插入排序或者冒泡排序。
3，如果待排序的集合规模较大，则应采用时间复杂度O(nlogn)的排序方法，如快速排序，堆排序或归并排序。
当待排序的元素是随机分布的，快速排序是平均时间最短的；
堆排序虽然时间复杂度跟快速排序一样，但是实际上的时间消耗(建堆，调整堆)会比快速排序多，因此一般选择快速排序。
但是相比快速排序，堆排序的空间的优点是占用更少，也不像快速排序，会出现最坏的情况。
如果需要稳定的排序算法，则可选归并排序。
4，堆排序适用于在一个集合n中，快速找出前m个元素(m<n)，每次建堆，调整堆，都找出一个元素，执行m次则找出前m个元素。
5，如果待排序的数据比较集中。则可以采用计数排序。
6，实际算法使用时，可以多个算法一起使用，以达到更好的效果。如归并排序中，桶排序中，对子串的处理都可以选择其他效率更好的算法。
每个算法代码可见：https://github.com/yangwu/JavaDemo