前言十大排序
一 冒泡排序
冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
原理：每次比较前后两个值
- 比较相邻元素。如果前一个元素比后一个元素大，则交换这两个元素位置。
- 对每一对元素重复操作，直至比较完成。
1.1 代码实现
/*** 冒泡排序* @param array* @return*/public static int[] bubbleSort(int[] array) {int len = arr.length;//从0开始，依次向后遍历，每次把最大的移动到最后for (int i = 0; i < len; i++) {//出勤最后的大值，比较前面的乱序for (int j = 0; j < len - i - 1; j++) {if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}return arr;}public static void main(String[] args) {System.out.println(JSONObject.toJSONString(SortTest.bubbleSort(new int[]{6, 5, 4, 3, 2, 1})));}
1.2 总结
- 最佳情况：T(n) = O(n)
- 最差情况：T(n) = O(n2)
- 平均情况：T(n) = O(n2)
二 选择排序
选择排序(Selection-sort)是一种简单直观的排序算法。
原理：每次获取最小值
- 每次遍历，都假定第一个索引处元素是最小值，然后和其他索引处值依次进行比较，如果当前索引处值大于其他某个索引处值，那么其他索引处值为最小值，交换第一个索引处和最小值所在索引处值。
- 以此类推，最后可以找到最小值所在索引。
2.1 代码实现
/**
* 选择排序
*
* @param array
* @return
*/
public static int[] selectionSort(int[] arr) {
int len = arr.length;
//从0开始，假设第一个数最小，依次向后假设
for (int i = 0; i < len - 1; i++) {
int minIndex = i;
//每次与最小的值比较后面的数据，有最小的向前提取。
for (int j = i; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
public static void main(String[] args) {
System.out.println(JSONObject.toJSONString(SortTest.selectionSort(new int[]{6, 5, 4, 3, 2, 1})));
}
2.2 总结
- 把所有的元素分为两组，已经排序的和未排序的；
- 找到未排序组中第一个元素，向已经排序组中进行插入；
3.1 代码实现
/**
* 插入排序
*
* @param array
* @return
*/
public static int[] insertionSort(int[] arr) {
int len = arr.length;
//从一开始，每次新插一个
for (int i = 1; i < len; i++) {
//对新增后的分组，重新排序
for (int j = i; j > 0; j--) {
if (arr[j - 1] > arr[j]) {
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
return arr;
}
public static void main(String[] args) {
System.out.println(JSONObject.toJSONString(SortTest.insertionSort(new int[]{6, 5, 4, 3, 2, 1})));
}
3.2 总结
- 最佳情况：T(n) = O(n)
- 最坏情况：T(n) = O(n2)
- 平均情况：T(n) = O(n2)
四 希尔排序
1959年Shell发明，第一个突破O(n)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序**。
原理：**
- 选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组；
- 对分好组的每一组数据完成插入排序；
- 减小增长量，最小减为1，重复第二步操作。
增长量h的确定：增长量h的值每一固定的规则，我们这里采用以下规则：
int h=1
while(h<5){
h=2h+1；//3,7
}
//循环结束后我们就可以确定h的最大值；
h的减小规则为：
h=h/2
4.1 代码实现
package com.ycc.data.sort;
import com.alibaba.fastjson.JSONObject;
/**
* 希尔排序
*
* @author hezhaoming
* @date 2020/10/19
*/
public class ShellSort {
public static void main(String[] args) {
int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
int len = arr.length;
int gap = len / 2;
int temp;
while (gap > 0) {
//找到每一个待插入元素 加入gap=4，i=4，gap=4，i=5，gap=4，i=6
for (int i = gap; i < len; i++) {
//把待插入的元素插入到有序数列中 比较 0-5，1-6，2-7
for (int j = i; j >= gap; j -= gap) {
if (arr[j - gap] > arr[j]) {
temp = arr[j];
arr[j] = arr[j - gap];
arr[j - gap] = temp;
} else {
break;
}
}
}
gap = gap / 2;
}
System.out.println(JSONObject.toJSONString(arr));
}
}
4.2 总结
- 最佳情况：T(n) = O(nlog2 n)
- 最坏情况：T(n) = O(nlog2 n)
- 平均情况：T(n) = O(nlog2n)
五 归并排序
是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
原理：
- 尽可能将数据拆分成两个元素相等子组，并对每个子组继续拆分，直到每个子组元素个数是1为止。
- 将相邻的两个子组进行合并成一个有序的大组；
- 不断的重复步骤2，直到最终只有一个组为止。
5.1 代码实现
package com.ycc.data.sort;
import com.alibaba.fastjson.JSONObject;
/**
* 归并排序
*
* @author 何兆明
* @description 如果要排序一个数组，我们先把数组从中间分成前后两部分，然后分别对前后两部分进行排序，再将排好序的两部分数据合并在一起就可以了
* @create 2019-04-09 11:33
*/
public class MergeSort {
public static void main(String[] args) {
int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 2, 4};
int len = arr.length;
int[] temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
sort(arr, 0, arr.length - 1, temp);
System.out.println(JSONObject.toJSONString(arr));
}
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 li = left;//左序列指针
int ri = mid + 1;//右序列指针
int t = 0;//临时数组指针
while (li <= mid && ri <= right) {
//左边小于右边
if (arr[li] <= arr[ri]) {
temp[t++] = arr[li++];
} else {
temp[t++] = arr[ri++];
}
}
//左边提前结束，将左边剩余元素填充进temp中
while (li <= mid) {
temp[t++] = arr[li++];
}
//将右序列剩余元素填充进temp中
while (ri <= right) {
temp[t++] = arr[ri++];
}
t = 0;
//将temp中的元素全部拷贝到原数组中
while (left <= right) {
arr[left++] = temp[t++];
}
}
}
5.2 总结
- 最佳情况：T(n) = O(n)
- 最差情况：T(n) = O(nlogn)
- 平均情况：T(n) = O(nlogn)
六 快速排序
快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
原理：
- 首先设定一个分界值，通过该分界值将数组分成左右两部分。
- 将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
- 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
- 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。
6.1 代码实现
package com.ycc.power;
import com.alibaba.fastjson.JSONObject;
/**
* 快速排序
* @author 何兆明
* @description
* @create 2019-04-11 17:27
*/
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
int left, right, temp, t;
if (low > high) {
return;
}
left = low;
right = high;
//temp就是基准位
temp = arr[low];
while (left < right) {
//先看右边，依次往左递减
while (temp <= arr[right] && left < right) {
right--;
}
//再看左边，依次往右递增
while (temp >= arr[left] && left < right) {
left++;
}
//如果满足条件则交换
if (left < right) {
t = arr[right];
arr[right] = arr[left];
arr[left] = t;
}
}
//最后将基准为与i和j相等位置的数字交换
arr[low] = arr[left];
arr[left] = temp;
//递归调用左半数组
quickSort(arr, low, right - 1);
//递归调用右半数组
quickSort(arr, right + 1, high);
}
public static void main(String[] args) {
int[] arr = {10, 7, 2, 4, 7, 62, 3, 4, 2, 1, 8, 9, 19};
quickSort(arr, 0, arr.length - 1);
System.out.println(JSONObject.toJSONString(arr));
}
}
6.2 总结
- 最佳情况：T(n) = O(nlogn)
- 最差情况：T(n) = O(n2)
- 平均情况：T(n) = O(nlogn)
七 堆排序
堆排序（Heapsort） 是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。7.1 代码实现
```java package com.ycc.power;
import com.alibaba.fastjson.JSONObject;
/**
- @author 何兆明
- @description 堆就是一个完全二叉树；最大堆根节点大于子节点，最小堆根节点小于子节点
@create 2019-04-10 15:12 */ public class HeapSort {
// 构建堆 public static void buildMaxHeap(int[] array) {
if (array == null || array.length == 1) return; // 堆的公式就是 int root = 2*i, int left = 2*i+1, int right = 2*i+2; int cursor = array.length / 2; for (int i = cursor; i >= 0; i--) { // 这样for循环下，就可以第一次排序完成// maxHeap(array, array.length, i);
minHeap(array, array.length, i); }}
// 最大堆 public static void maxHeap(int[] array, int heapSieze, int index) {
int left = index * 2 + 1; // 左子节点 int right = index * 2 + 2; // 右子节点 int maxValue = index; // 暂时定在Index的位置就是最大值 // 如果左子节点的值，比当前最大的值大，就把最大值的位置换成左子节点的位置 if (left < heapSieze && array[left] > array[maxValue]) { maxValue = left; } // 如果右子节点的值，比当前最大的值大，就把最大值的位置换成右子节点的位置 if (right < heapSieze && array[right] > array[maxValue]) { maxValue = right; } // 如果不相等，说明啊，这个子节点的值有比自己大的，位置发生了交换了位置 if (maxValue != index) { swap(array, index, maxValue); // 就要交换位置元素 // 交换完位置后还需要判断子节点是否打破了最大堆的性质。最大堆性质：两个子节点都比父节点小。 maxHeap(array, heapSieze, maxValue); }}
// 最小堆 public static void minHeap(int[] array, int heapSieze, int index) {
int left = index * 2 + 1; // 左子节点 int right = index * 2 + 2; // 右子节点 int maxValue = index; // 暂时定在Index的位置就是最小值 // 如果左子节点的值，比当前最小的值小，就把最小值的位置换成左子节点的位置 if (left < heapSieze && array[left] < array[maxValue]) { maxValue = left; } // 如果右子节点的值，比当前最小的值小，就把最小值的位置换成左子节点的位置 if (right < heapSieze && array[right] < array[maxValue]) { maxValue = right; } // 如果不相等，说明啊，这个子节点的值有比自己小的，位置发生了交换了位置 if (maxValue != index) { swap(array, index, maxValue); // 就要交换位置元素 // 交换完位置后还需要判断子节点是否打破了最小堆的性质。最小性质：两个子节点都比父节点大。 minHeap(array, heapSieze, maxValue); }}
// 数组元素交换 public static void swap(int[] array, int index1, int index2) {
int temp = array[index1]; array[index1] = array[index2]; array[index2] = temp;}
public static void heapSort(int[] array) {
if (array == null || array.length == 1) return; buildMaxHeap(array); // 第一次排序，构建最大堆，只保证了堆顶元素是数组里最大的 for (int i = array.length - 1; i >= 1; i--) { // 这个是什么意思呢？，经过上面的一些列操作，目前array[0]是当前数组里最大的元素，需要和末尾的元素交换 // 然后，拿出最大的元素 swap(array, 0, i); // 交换完后，下次遍历的时候，就应该跳过最后一个元素，也就是最大的那个值，然后开始重新构建最大堆 // 堆的大小就减去1，然后从0的位置开始最大堆// maxHeap(array, i, 0);
minHeap(array, i, 0); }}
public static void main(String[] args) {
int[] array = {19, 38, 7, 36, 5, 5, 3, 2, 1, 0, 56};
System.out.println("排序前:" + JSONObject.toJSONString(array));
System.out.println("分割线---------------");
heapSort(array);
System.out.println("排序后:" + JSONObject.toJSONString(array));
}
}
7.2 总结
八 计数排序
8.1 代码实现
8.2 总结
计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。
九 桶排序(Bucket Sort）
9.1 代码实现
9.2 总结
十 基数排序(Radix Sort)
10.1 代码实现
10.2 总结
若有收获，就点个赞吧
0 人点赞
