基本排序算法总结
原文：https://blog.csdn.net/qq_21187515/article/details/127212565
一直想总结一下最常用的排序算法，自己写一下代码并运行一下记忆更深刻
1、插入排序
-
说明
每步将一个待排序的记录，按其排序码大小，插到前面已经排序的文件中的适当位置，直到全部插入完为止。
原理：从待排序的n个记录中的第二个记录开始，依次与前面的记录比较并寻找插入的位置，每次外循环结束后，将当前的数插入到合适的位置。
-
平均时间复杂度
平均复杂度 O(n²)
最好情况 O(n)
最坏情况 O(n²)
空间复杂度O(1);
稳定性 稳定 -
适用场景
插入排序由于O( n2 )的复杂度，在数组较大的时候不适用。它适用于简单数据排序。 -
代码
/**
* 简单插入排序
*/
public class InsertSort {
public static void insertSort(int[] arr){
int temp;
int length = arr.length;
for(int i=1;i<length;i++){
int j = i-1;
temp = arr[i];
while(j>=0 && arr[j] > temp){
arr[j+1] = arr[j];
j--;
}
if(j != i-1){
arr[j+1] = temp;
}
}
}
}
2、希尔排序
- 说明
在希尔排序出现之前，计算机界普遍存在“排序算法不可能突破O(n2)”的观点。希尔排序是第一个突破O(n2)的排序算法，它是简单插入排序的改进版。
希尔排序是对直接插入排序的改进算法。希尔排序是通过分组+插入，先分组再插入。
-
平均时间复杂度
平均复杂度 O(nlogn)
最好情况 O(n log²n)
最坏情况 O(n log²n)
空间复杂度O(1)
稳定性 不稳定 -
适用场景
Shell排序虽然快，但是毕竟是插入排序，其数量级并没有后起之秀–快速排序O(n㏒n)快。在大量数据面前，Shell排序不是一个好的算法。但是，中小型规模的数据完全可以使用它。 -
代码
/**
* 快速排序
*/
public class QuickSort {
public static void quickSort(int[] arr,int start,int end){
if(start>end) return;
int left = start;
int right = end;
int base = arr[start];
while(left != right){
while(left<right && arr[right]>=base){right--;}
while(left<right && arr[left] <= base){left++;}
if(left<right){
swap(arr,left,right);
}
}
swap(arr,start,left);
quickSort(arr,start,left-1);
quickSort(arr,left+1,end);
}
public static void swap(int[] arr,int left,int right){
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
3、冒泡排序
- 说明
交换排序的基本方法是：两两比较待排序记录的排序码，交换不满足顺序要求的偶对，直到全部满足位置。常见的冒泡排序和快速排序就属于交换类排序。
算法思想： 从数组中第一个数开始，依次遍历数组中的每一个数，通过相邻比较交换，每一轮循环下来找出剩余未排序数的中的最大数并”冒泡”至数列的顶端。
-
平均时间复杂度：O(n2)
平均复杂度 O(n²)
最好情况 O(n)
最坏情况 O(n²)
空间复杂度O(1)
稳定性 稳定 -
适用场景
它适用于简单数据排序。 -
代码
/**
* 冒泡排序
*/
public class BubleSort {
public static void bubbleSort(int[] array){
int length = array.length;
for(int i=0;i<=length-1;i++){
boolean swap = Boolean.FALSE;
for(int j=0;j<length-1-i;j++){
if(array[j]>array[j+1]){
swap(array,j,j+1);
swap = Boolean.TRUE;
}
}
if(!swap){
//已经没有交换了，跳出循环
break;
}
}
}
/**
* 交换函数
* @param array
* @param left
* @param right
*/
public static void swap(int[] array,int left,int right){
// 算法一
int temp = array[left];
array[left] = array[right];
array[right] = temp;
// 算法二
// array[left] = array[left] +array[right];
// array[right] = array[left] - array[right];
// array[left] = array[left] - array[right];
}
}
4、快速排序
- 说明
快速排序是一个既高效又不浪费空间的一种排序算法，面试问排序的基本题。
快速排序是对冒泡排序的改进算法，快速排序采用的思想是分治思想。
冒泡排序是在相邻的两个记录进行比较和交换，每次交换只能上移或下移一个位置，导致总的比较与移动次数较多。快速排序简单来说就是定义一个标准，大于标准的放一边，小于标准的方另一边，再递归。
-
平均时间复杂度
平均复杂度 O(nlogn)
最好情况 O(nlogn)
最坏情况 O(n²)
空间复杂度O(logn)
稳定性 不稳定 -
适用场景
快速排序在大多数情况下都是适用的，尤其在数据量大的时候性能优越性更加明显。但是在必要的时候，需要考虑下优化以提高其在最坏情况下的性能。 -
代码
/**
* 快速排序
*/
public class QuickSort {
public static void quickSort(int[] arr,int start,int end){
if(start>end) return;
int left = start;
int right = end;
int base = arr[start];
while(left != right){
while(left<right && arr[right]>=base){right--;}
while(left<right && arr[left] <= base){left++;}
if(left<right){
swap(arr,left,right);
}
}
swap(arr,start,left);
quickSort(arr,start,left-1);
quickSort(arr,left+1,end);
}
public static void swap(int[] arr,int left,int right){
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
5、简单选择排序
-
说明
选择类排序的基本方法是：每步从待排序记录中选出排序码最小的记录，顺序放在已排序的记录序列的后面，直到全部排完。
-
时间复杂度
平均复杂度 O(n²)
最好情况 O(n²)
最坏情况 O(n²)
空间复杂度O(1)
稳定性 不稳定 -
适用场景
选择排序实现也比较简单，由于固有的O(n2)复杂度，选择排序在海量数据面前显得力不从心。因此，它适用于简单数据排序。 -
代码
/**
* 简单选择排序
*/
public class SelectionSort {
public static void selectionSort(int[] arr){
int length = arr.length;
int minIndex;
for(int i=0;i<length -1;i++){
minIndex = i;
for(int j= i+1;j<=length-1;j++){
if(arr[j] < arr[minIndex]){
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
6、堆排序
-
说明
-
平均时间复杂度
平均复杂度 O(nlongn)
最好情况 O(nlogn)
最坏情况 O(nlogn)
空间复杂度O(1)
稳定性 不稳定 -
适用场景
堆排序在建立堆和调整堆的过程中会产生比较大的开销，在元素少的时候并不适用。但是，在元素比较多的情况下，还是不错的一个选择。尤其是在解决诸如“前n大的数”一类问题时，几乎是首选算法。 -
代码