把温柔和例外留给值得的人：比如你
大家好，这里是新一，请多关照🙈🙉🙊。我们不管是在做题中还是在面试中，哦排序算法都有所涉猎，所以新一在本篇博客总结了常见的排序算法，干货满满哟。（以下结果均在IDEA中编译）希望在方便自己复习的同时也能帮助到大家。😜😜😜🎪🚀🧰
以下是我们的文章
文章目录
一.🎪 基于比较的排序算法
常见基于比较的排序算法有以下七种：
1.1 🚀 插入排序
我们这里介绍直接插入排序和折半插入排序。
🧰 直接插入排序
public static void insertSort(int[] array){
for (int i = 0; i < array.length; i++) {
//傀儡变量保存节点值
int tmp = array[i];
int j = i - 1;
for (;j >= 0; j--){
if (array[j] > tmp){
array[j + 1] = array[j];
}else{
break;//找到合适位置退出循环
}
}
array[j + 1] = tmp;//插入排序
}
}
🧰 折半插入排序
//折半插入排序
public static void bsinsertSort(int[] array){
for (int i = 0; i < array.length; i++) {
int ret = array[i];
int left = 0;
int right = i;
//由于插入排序数据会逐渐趋于有序，所以可用折半查找节点值
while (left < right){
int mid = left + (right - left) / 2;
if (array[mid] < ret){
left = mid + 1;
}else {
right = mid;
}
}
for (int j = i - 1; j >= left; j--) {
array[j + 1] = array[j];
}
array[left] = ret;
}
}
稳定性：稳定
插入排序，初始数据越接近有序，时间效率越高。
1.2 🚀 希尔排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
- 希尔排序是对直接插入排序的优化。
- 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
//希尔排序
public static void shellSort(int[] array){
int gap = array.length;
while (gap > 1){
shell(array, gap);
gap /= 2;
}
shell(array, 1);
}
public static void shell(int[] array, int gap){
for (int i = 0; i < array.length; i++) {
int ret = array[i];
int j = i - gap;
for (; j >= 0; j -= gap) {
if (array[j] > ret){
array[j + gap] = array[j];
}else{
break;
}
}
array[j + gap] = ret;
}
}
稳定性：不稳定
1.3 🚀 选择排序
每一次从无序区间选出最大（或最小）的一个元素，存放在无序区间的最后（或最前），直到全部待排序的数据元素排完 。
🧰 单向选择排序
//交换
public static void swap(int[] array, int i, int j){
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
//选择排序
public static void selectSort(int[] array){
for (int i = 0; i < array.length; i++) {
int min = i;
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[min]){
min = j;
}
}
swap(array, i, min);
}
}
🧰 双向选择排序
//双向选择排序
public static void selectSortOP(int[] array){
int low = 0;
int high = array.length - 1;
while (low <= high){
int min = low;
int max = high;
for (int i = low + 1; i <= high; i++) {
if (array[i] < array[min]){
min = i;
}
if (array[i] > array[max]){
max = i;
}
}
swap(array, low, min);
if (max == low){
max = min;
}
swap(array, high, max);
low++;
high--;
}
}
稳定性：不稳定
1.4 🚀 堆排序
基本原理也是选择排序，只是不在使用遍历的方式查找无序区间的最大的数，而是通过堆来选择无序区间的最大的数。
注意： 排升序要建大堆；排降序要建小堆。
/**
* 堆排序
* 时间复杂度：O(n * log N)
* 空间复杂度：O(1)
* 稳定性：不稳定
* @param array
*/
public static void heapSort(int[] array){
createHeap(array);
for (int end = array.length - 1; end > 0; end--) {
swap(array, 0, end);
shiftDown(array, 0, end);
}
}
public static void createHeap(int[] array){
for (int parent = (array.length - 2) / 2; parent >= 0; parent--) {
shiftDown(array,parent,array.length);
}
}
public static void shiftDown(int[] array, int parent, int len){
int child = 2 * parent + 1;
while (child < len){
if (child + 1 < len && array[child] < array[child+ 1]) {
child++;
}
if (array[child] > array[parent]){
swap(array,child,parent);
parent = child;
child = child * 2 + 1;
}else{
break;
}
}
}
稳定性：不稳定
1.5 🚀 冒泡排序
在无序区间，通过相邻数的比较，将最大的数冒泡到无序区间的最后，持续这个过程，直到数组整体有序
/**
* 冒泡排序
* 时间复杂度：O(n^2)
* 空间复杂度：O(1)
* @param array
*/
public static void bubbleSort(int[] array){
for (int i = 0; i < array.length - 1; i++) {
boolean flg = false;
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]){
swap(array,j,j + 1);
flg = true;
}
}
if (flg == false){//优化
break;
}
}
}
稳定性：稳定
1.6 🚀 快速排序
- 从待排序区间选择一个数，作为基准值(pivot)；
- Partition: 遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的（可
以包含相等的）放到基准值的右边； - 采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间的长度 == 1，代表已经有序，或者小区间的长度 == 0，代表没有数据
🧰 递归分治
/**
* 快速排序
* 时间复杂度:
* 最好：O(k*n*logn) 快排中k小一点
* 最坏：O(n^2) - 单分支树
* 空间复杂度:
* 最好：O(logn)
* 最坏：O(n)
* 优化：基准优化 1.随机 2.三数取中法 3.把和基准相同的的数据移到跟前来
* 4.利用直接插入排序,优化算法
* 不稳定排序
* @param array 待排序数组
*/
public static void quickSort(int[] array){
quick(array,0, array.length - 1);
}
public static void quick(int[] array, int left, int right){
if (left >= right){
return;
}
if (right - left + 1 <= 1600){
insertSort(array, left, right);
return;
}
//1.找基准之前,我们找到中间大小的值
int midValIndex = findMidValIndex(array, left, right);
swap(array,midValIndex,left);
int pivot = partition(array, left, right);
quick(array, left, pivot - 1);
quick(array, pivot + 1, right);
}
private static int findMidValIndex(int[] array, int start, int end){
int mid = start + ((end - start) >>> 1);
if (array[start] < array[end]){
if (array[mid] < array[start]){
return start;
}else if(array[mid] > array[end]){
return end;
}else{
return mid;
}
}else{
if (array[mid] > array[start]){
return start;
}else if (array[mid] < array[end]){
return end;
}else{
return mid;
}
}
}
public static int partition(int[] array, int start, int end){
int tmp = array[start];
while (start < end){
while (start < end && array[end] >= tmp){
end--;
}
array[start] = array[end];
while (start < end && array[start] <= tmp){
start++;
}
array[end] = array[start];
}
array[start] = tmp;
return start;
}
🧰 非递归分治
/**
* 非递归快排
* @param array
*/
public static void quickSort1(int[] array){
Stack<Integer> stack = new Stack<>();
int left = 0;
int right = array.length - 1;
int pivot = partition(array, left, right);
if (pivot > left + 1){
stack.push(left);
stack.push(pivot - 1);
}
if (pivot < right - 1){
stack.push(pivot + 1);
stack.push(right);
}
while (!stack.isEmpty()){
right = stack.pop();
left = stack.pop();
pivot = partition(array, left, right);
if (pivot > left + 1){
stack.push(left);
stack.push(pivot - 1);
}
if (pivot < right - 1){
stack.push(pivot + 1);
stack.push(right);
}
}
}
1.7 🚀 归并排序
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
🧰 递归归并
/**
* 归并排序
* 时间复杂度：O(n * logn)
* 空间复杂度：O(n)
* 稳定性：稳定的排序
* 稳定的排序算法：插入 归并 冒泡
* @param array
*/
public static void mergeSort(int[] array){
mergeSortInternal(array,0,array.length - 1);
}
private static void mergeSortInternal(int[] array, int low, int high){
if (low >= high){
return;
}
int mid = low + ((high - low) >>> 1);
mergeSortInternal(array, low, mid);
mergeSortInternal(array, mid + 1, high);
merge(array,low,mid,high);
}
private static void merge(int[] array,int low, int mid, int high){
int[] tmp = new int[high - low + 1];
int k = 0;
int s1 = low;
int e1 = mid;
int s2 = mid + 1;
int e2 = high;
while (s1 <= e1 && s2 <= e2){
if (array[s1] < array[s2]){
/*tmp[k] = array[low];
low++;
k++;*/
tmp[k++] = array[s1++];
}else{
/*tmp[k] = array[mid + 1];
mid+ +;
k++;*/
tmp[k++] = array[s2++];
}
}
while (s1 <= e1){
tmp[k++] = array[s1++];
}
while (s2 <= e2){
tmp[k++] = array[s2++];
}
//拷贝tmp数组的元素，放入原来的数组当中
for (int i = 0; i < k; i++) {
array[i + low] = tmp[i];
}
}
🧰 非递归归并
/**
* 归并排序 - 非递归版
* @param array
*/
public static void mergeSort1(int[] array){
int nums = 1;
while (nums < array.length){
//数组每次都要进行遍历
for (int i = 0; i < array.length; i += nums * 2) {
int left = i;
int mid = left + nums - 1;
if (mid >= array.length){
mid = array.length - 1;
}
int right = mid + nums;
if (right >= array.length){
right = array.length - 1;
}
//下标确定之后
merge(array, left, mid, right);
}
nums *= 2;//分组
}
}
🧰 海量数据排序
外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G，需要排序的数据有 100G因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序
- 先把文件切分成 200 份，每个 512 M
- 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
- 进行 200 路归并，同时对 200 份有序文件做归并过程，最终结果就有序了
二.🎪 基于非比较的排序算法
三.🎪 思维导图
