基本排序算法比较
| 基本排序算法 | 平均时间复杂度 | 最好时间复杂度 | 最差时间复杂度 | 空间复杂度 | 稳定排序否 | 原地排序否 | 优点 | 缺点 |
|---|---|---|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n)* | O(n^2) | O(1) | 是 | 是 | - | - |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 否 | 是 | - | - |
| 插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 是 | 是 | - | - |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n)* | 是 | 否 | 稳定 | 需额外空间 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2)* | O(1) | 否 | 是 | 不需要额外空间 | 不稳定* |
| 桶排序 | O(n) | O(n) | O(n) | O(n) | 否 | 否 | 时间复杂度低 | 对数据范围和分布要求极严格 |
| 计数排序 | O(n) | O(n) | O(n) | O(n) | 可是可不是* | 否 | 时间复杂度低 | 对数据范围要求极严格 |
| 基数排序 | O(n) | O(n) | O(n) | O(n) | 是 | 否 | 时间复杂度低 | 对数据范围要求严格 |
说几点：
- 排序的本质是什么？将逆序对变成正序对 --- 衍生出一道题：求一个数组的逆序对？
- 平均时间复杂度：是所有不同逆序对组合排序时间复杂度的平均值，从0对到n*(n-1)/2;
最好时间复杂度：当数组有序时的时间复杂度
最坏时间复杂度：当数组逆序或者每次都得不到理想的结果 - 稳定排序判断：排序过程中是否能保证相同元素的前后位置保持不变；
这个指标对于基本类型数组排序没有区别；
但是对于对象数组是有区别的，因为对象数组排序可能会根据多个字段维度排序：先根据字段1排序再根据字段2排序，如果根据字段2排序是不稳定的，则相同字段2的值元素之前根据字段1排的序就白费了
比如：淘宝订单先根据下单时间字段排序，然后根据下单金额排序，排序完之后我们希望相同金额的单内部是按时间排序的，则按下单金额排序就必须采用稳定排序了；
所以，根据不同场景决定是否采用稳定排序。 - 每个排序算法说一下注意点：
- 冒泡排序：可以优化外层循环次数，当没有再进行swap时，则不用再继续了
- 归并排序：当数组较大的时候，消耗的空间为O(n)，可能就不大适合；还有一点，你可能发现了每次一分为二的时候都会new一个数组，空间复杂度不应该是O(nlogn)吗？空间复杂度不是这么算法的，空间复杂度是只某一时间占用额外内存的最大值，这里是单线程，每次new完一个数组使用之后会销毁掉，所以最多占用O(n)的空间
- 快排最差时间复杂度为O(n^2)出现的场景：每次partition后都是一分为1和n-1
- 计数排序：可稳定可不稳定，可以有两种写法，见后面的代码部分。
- 具体选择哪个排序算法，要看排序数字的大小，分布规律，是否要求稳定排序等因素。
- 扩展题
- 求一个数组的逆序对
归并过程中求解 - O(n)时间复杂度求数组第k大的元素
快排算法思想+减治法 - 10个接口访问10个日志文件，每个日志文件大小300M且都是按照时间排序的，将其合并成一个文件，但是限制内存大小只有1G，问怎么搞？
归并算法的merge过程，可以先假定只有两个1G的日志文件怎么搞 - D，a，F，B，c，A，z，b,只有大小写字母，排序将小写字母全部放在大写字母后面，小写字母或者大写字母之间不要求有序? 再问只有大小写字母和数字，将小写字母放左边，数字放中间，大写字母放右边，内部不要求有序，怎么搞？
外部排序首选：桶排序
各种排序算法实现和优化
- 冒泡排序
/**
* 描述：冒泡排序
*
* @author xuery
* @date 2018/11/20
*/
public class BubbleSort {
private static final int ARR_SIZE = 10;
public static void main(String[] args) {
int[] arr = ArrayUtil.generateArray(ARR_SIZE, 50);
optimizeBubbleSort(arr);
ArrayUtil.printArray(arr);
}
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
//注意这里不能大于等于，有等于则是非稳定排序
if(arr[j] > arr[j+1]){
ArrayUtil.swap(arr, j ,j+1);
}
}
}
}
public static void optimizeBubbleSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
for (int i = 0; i < arr.length - 1; i++) {
boolean continueFlag = false;
for (int j = 0; j < arr.length - 1 - i; j++) {
//注意这里不能大于等于，有等于则是非稳定排序
//优化，如果当前内层循环一次都没有进入到swap则说明已经有序了，不需要往下进行了
if(arr[j] > arr[j+1]){
ArrayUtil.swap(arr, j ,j+1);
continueFlag = true;
}
}
if (!continueFlag){
break;
}
}
}
}
- 选择排序
/**
* 描述：选择排序
*
* @author xuery
* @date 2018/11/20
*/
public class SelectSort {
private static final int ARR_SIZE = 10;
public static void main(String[] args) {
int[] arr = ArrayUtil.generateArray(ARR_SIZE, 50);
selectSort(arr);
ArrayUtil.printArray(arr);
}
public static void selectSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
if (minIndex != i) {
ArrayUtil.swap(arr, i, minIndex);
}
}
}
}
- 插入排序
/**
* 描述：插入排序
*
* @author xuery
* @date 2018/11/20
*/
public class InsertSort {
public static void main(String[] args) {
int[] arr = ArrayUtil.generateArray(10, 50);
insertSort(arr);
ArrayUtil.printArray(arr);
}
public static void insertSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
for (int i = 1; i < arr.length; i++) {
//从下表i-1遍历到0找到arr[i]插入的位置
int insertIndex = 0;
int arri = arr[i];
for (int j = i - 1; j >= 0; j--) {
//注意，这里也不能取等号，否则就是不稳定排序了
if(arr[j] > arri){
arr[j+1] = arr[j];
} else {
insertIndex = j+1;
break;
}
}
arr[insertIndex] = arri;
}
}
}
- 归并排序
/**
* 描述：归并排序及非递归实现
*
* @author xuery
* @date 2018/11/20
*/
public class MergeSort {
public static void main(String[] args) {
int[] arr = ArrayUtil.generateArray(7, 50);
MergeSort mergeSort = new MergeSort();
ArrayUtil.printArray(arr);
mergeSort.notRecursionMergeSort(arr);
ArrayUtil.printArray(arr);
}
public void mergeSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
recursionMergeSort(arr, 0, arr.length - 1);
}
public void recursionMergeSort(int[] arr, int begin, int end) {
if (begin >= end) {
return;
}
int mid = begin + (end - begin) / 2;
//divide into two parts
recursionMergeSort(arr, begin, mid);
recursionMergeSort(arr, mid + 1, end);
//merge
int[] temp = new int[end - begin + 1];
int i = begin, j = mid + 1, index = 0;
while (i <= mid && j <= end) {
//这里需要有等号，保证稳定性
if (arr[i] <= arr[j]) {
temp[index++] = arr[i++];
} else {
temp[index++] = arr[j++];
}
}
while (i <= mid) {
temp[index++] = arr[i++];
}
while (j <= end) {
temp[index++] = arr[j++];
}
//将temp复制会arr对应的位置
for (int k = 0; k < end - begin + 1; k++) {
arr[k + begin] = temp[k];
}
}
/**
* 非递归实现归并排序
* 思路很简单：就是没有递，只有归，先1+1合并，再2+2合并，最后n/2+n/2合并
* 如何编写代码：自己举例，确定两两合并的边界，边界一旦确定直接采用之前的merge就可以了
* 注意点：两两个数不一定相同，要注意越界条件等的判断
*
* bug:一定要注意对某些变量操作完之后，它已经不代表最初的值了，想要最初的值就不能对变量操作或者新建一个变量保存最初的值
* @param arr
*/
public void notRecursionMergeSort(int[] arr) {
//step表示step个元素+step个元素合并
int step = 1;
while (step < arr.length) {
for (int i = 0; i < arr.length; i = i + 2 * step) {
//i--i+step-1合并，i+step--i+2*step-1合并，都包括边界，注意越界条件判断
//i+step>=arr.length时右边一半没有，结束本step合并
if (i + step >= arr.length) {
break;
}
//可以开始合并
int mid = i + step - 1, right = Math.min(i + 2 * step - 1, arr.length - 1);
int[] temp = new int[right - i + 1];
int leftIndex = i, rightIndex = mid + 1, index = 0;
while (leftIndex <= mid && rightIndex <= right) {
if (arr[leftIndex] <= arr[rightIndex]) {
temp[index++] = arr[leftIndex++];
} else {
temp[index++] = arr[rightIndex++];
}
}
while (leftIndex <= mid) {
temp[index++] = arr[leftIndex++];
}
while (rightIndex <= right) {
temp[index++] = arr[rightIndex++];
}
for (int k = 0; k < right - i + 1; k++) {
arr[k + i] = temp[k];
}
}
step = step * 2;
}
}
}
- 快速排序
/**
* 描述：快排填坑法再搞一遍
* 非稳定排序，相同值可能由于partition导致顺序改变
*
* @author xuery
* @date 2018/11/20
*/
public class QuickSort2 {
private static final Random random = new Random();
public static void main(String[] args) {
int[] arr = ArrayUtil.generateArray(10, 20);
ArrayUtil.printArray(arr);
quickSort(arr);
ArrayUtil.printArray(arr);
}
public static void quickSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int begin, int end) {
if (begin >= end) {
return;
}
int partition = partition(arr, begin, end);
//divide into three parts including [begin,partition-1],partition,[partition+1,end]
quickSort(arr, begin, partition - 1);
quickSort(arr, partition + 1, end);
}
//挖坑：第一个坑是基准所在的位置，最后一个坑填基准值，填坑条件：与基准值比较，每次循环填两个坑，一左一右
public static int partition(int[] arr, int begin, int end) {
//随机取其中的一个值作为基准并与最后一个值交换
int pIndex = begin + random.nextInt(end - begin + 1);
if (pIndex != end) {
ArrayUtil.swap(arr, pIndex, end);
}
int pivot = arr[end];
int i = begin, j = end;
while (i < j) {
//从左往右找第一个大于pivot的
while (i < j && arr[i] <= pivot) {
i++;
}
if (i < j) {
arr[j] = arr[i];
j--;
}
//从右往左找第一个小于pivot的
while (i < j && arr[j] >= pivot) {
j--;
}
if (i < j) {
arr[i] = arr[j];
i++;
}
}
arr[i] = pivot;
return i;
}
}
- 计数排序
/**
* 描述：计数排序
* <p>
* 算法描述：如其名，遍历数组，数组中的值对应计数数组的下标，将对应计数数组下标对应的值+1操作；之后再遍历计数数组即可完成排序
* <p>
* 要求数组中元素的值分布在某个比较小的范围内
* <p>
* 可以是不稳定排序或者稳定排序
*
* @author xuery
* @date 2018/11/20
*/
public class CountSort {
public static void main(String[] args) {
int[] arr = ArrayUtil.generateArray(10, 20);
ArrayUtil.printArray(arr);
stableCountSort(arr);
ArrayUtil.printArray(arr);
}
/**
* 不稳定的计数排序，无法保证相同数值保证顺序不变，因为是采用从头到尾直接遍历计数数组的方式
* <p>
* 假设只有非负整数
*
* @param arr
*/
public static void notStableCountSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
//find max value
int maxValue = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
if (maxValue < arr[i]) {
maxValue = arr[i];
}
}
//new a counting arr to count now
int[] countArr = new int[maxValue + 1];
for (int i = 0; i < arr.length; i++) {
countArr[arr[i]]++;
}
int index = 0;
for (int i = 0; i < countArr.length; i++) {
while (countArr[i]-- > 0) {
arr[index++] = i;
}
}
}
/**
* 上面的方式是不稳定排序，可以采用比较巧妙的方法改写成稳定排序
* <p>
* 从头遍历countArr数组，将之前的数值累加到当前位置并放入countSumArr数组中，这样countSumArr[i]就表示当前小于等于i的数值个数为countSumArr[i]
* 然后从尾部开始遍历countArr, 比如遍历到countArr[i],根据对应的countSumArr[i]的值就知道应该把i放回原数组arr的哪个位置，
* 并将countArr[i]和countSumArr[i]分别减一, 对于countArr重复该操作，直至countArr[i]变为0
* 这样可以巧妙的保证相同数值的元素顺序保持不变
*
* @param arr
*/
public static void stableCountSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
//find max value
int maxValue = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
if (maxValue < arr[i]) {
maxValue = arr[i];
}
}
//new a counting arr to count now
int[] countArr = new int[maxValue + 1];
for (int i = 0; i < arr.length; i++) {
countArr[arr[i]]++;
}
//calcalate countSumArr just as explained
int[] countSumArr = new int[maxValue + 1];
countSumArr[0] = countArr[0];
for (int i = 1; i < countArr.length; i++) {
countSumArr[i] = countSumArr[i - 1] + countArr[i];
}
for (int i = countArr.length - 1; i >= 0; i--) {
while(countArr[i]-- > 0){
arr[--countSumArr[i]] = i;
}
}
}
}
