部分排序算法的总结
导读:
最近看了一些有关排序算法的东西，这里就是简单的记录一下。
主要是 ：（默认实现的 升序）
选择排序、插入排序、冒泡排序、快速排序、归并排序、堆排序。
选择排序
- 时间复杂度：O(n²)。
- 空间复杂度：O(1)。
- 主要思想： 就是2遍循环遍历数组，外层循环控制每个数字应该放的数字，内层循环找到这个数组的最小值，把它放到应该放到的位置（即外层循环控制的位置）上去。
- 代码： 注意在写代码时用数组的下标来找数组的相应的最小值，不要直接用值比较
，这样在后面要交换的时候 是 没有对数组的内部元素进行操作的。
public static void selectionSort(int[] arr) {
if(arr == null || arr.length < 1) {
return ;
}
for(int i = 0; i < arr.length; i++) {
int minIndex = i; // 要用下标来找，不能用数值来找，否则后面交换的时候不是在数组内交换的（总之就是交换不过来）
for(int j = i; j < arr.length; j++) {
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
swap(arr, i, minIndex);
}
}
// 对arr[a], arr[b] 这两个数进行交换
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
- 稳定性：不能做到稳定性。
比如数组 ： 2，3，2，6，6，6，1，2
这样排完了之后1在最前面，可是这些2的相对顺序也已经改变了。
插入排序
- 时间复杂度：O(n²)
- 空间复杂度：O(1)
- 主要思想： 可以想象打扑克牌时理牌的情形。
也是遍历2遍，一开始认为第一个数是排好的了，外层循环从1位置开始遍历，内存循环从外层循环的位置一直往前找，有顺序不符的就交换。
public static void insertionSort(int[] arr) {
if(arr == null || arr.length < 1) {
return ;
}
for(int end = 1; end < arr.length; end++) {
//[0...end-1]是已经排好的范围
for(int j = end; j > 0 && arr[j] < arr[j-1]; j--) {
//j不能到0，到0的话，下面的j-1会越界
swap(arr, j, j-1);
}
}
}
// 对arr[a], arr[b] 这两个数进行交换
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
- 稳定性： 可以做到稳定性。 就是在往前找的时候，如果遇到相等的数就不动、不交换就可以了，这样他们的相对顺序还是原来的那样。
冒泡排序
- 时间复杂度：O(n²)
- 空间复杂度：O(1)
- 主要思想：2个2个的数依次比较，大的数放在后面，这样完了后也就是有序的数组了。 因为整个过程很像 冒泡的过程，大的数都浮到了最后面。
- 代码：
public static void bubbleSort(int[] arr) {
if(arr == null || arr.length < 1) {
return ;
}
for(int end = arr.length-1; end >= 0; end--) {
for(int start = 0; start < end; start++) {
if(arr[start] > arr[start+1]) {
swap(arr, start, start+1);
}
}
}
}
// 对arr[a], arr[b] 这两个数进行交换
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
- 稳定性： 可以做到稳定性。 就是2个数在比较的时候，如果是相等的话不交换就好。
快速排序
- 时间复杂度：O(N*logN)
- 空间复杂度：O( logN ) 就是partition的过程，在找中点的时候用了一定的空间存储
- 主要思想：1. 先在数组中随机找一个数字（把这个数字放在数组的最右边或者最左边，最后再交换一下），再根据这个数组在数组中划分，小于的放一边，等于的放一边，大于的放一边。之后再对小于的、大于的部分递归调用这个过程，整个数组就是有序的了。 （这是最优化后的做法了）
- 但是在找这个数字的时候是随机找的，可以选用第一个数字或者最后一个数字。但是、but、however，这样的话，对于本来就是几乎有序的数组 来说，时间复杂度会退化到O(n²)。
- 还有一种是把小于等于的放一变，大于的放一边（或者小于的放一边，大于等于的放一边）。但是、but、however，这样的话，对于本来就有很多重复元素的数组来说，时间复杂度也会退化成O(n²)。因为这样每次划分只搞定了一个数字。
- 代码
public static void quickSortMain(int[] arr) {
if(arr == null || arr.length < 1) {
return ;
}
quickSort(arr, 0, arr.length-1);
}
public static void quickSort(int[] arr, int left, int right) {
if(left >= right) {
return ;
}
//记得这里有一个left的偏移.... 要保证在left到right的区间里...
swap(arr, left+(int)(Math.random()*(right-left+1)) , right);
int[] p = partition(arr, left, right); //partition返回的数组里只有2个数。
quickSort(arr, left, p[0]-1);
quickSort(arr, p[1]+1, right);
}
// 返回的第一个数是 等于部分的左闭区间， 第二个数是 等于部分的右闭区间
public static int[] partition(int[] arr, int left, int right) {
int less = left-1;
int more = right;
int index = left;
while(index < more) {
if(arr[index] < arr[right] ) {
swap(arr, index++, ++less);
} else if(arr[index] > arr[right]) {
swap(arr, index, --more);
} else {
// arr[index] == arr[right]
index++;
}
}
swap(arr, right, more);
return new int[] {
less+1, more};
}
// 对arr[a], arr[b] 这两个数进行交换
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
- 稳定性： 一般来说不能做到稳定性。 但是严格来讲是可以做到的，有兴趣的可以去搜索有关“01 stable sort”的资料。
归并排序
- 时间复杂度：O(N*logN)
- 空间复杂度：O(N) 要开辟辅助数组
- 主要思想：将数组二分二分的一直分下去，直到只剩1个数字的时候，认为他是排好的（只有1个数字，没有其他数字相比较，当然是排好的了），然后在从分的时候，2组2组的往上合并，在合并的过程中，先放2部分中最小的那个，把放的数字装到开辟的辅助数组中，然后再将这个辅助数组 放到 原数组中他对应应该在的位置。这样一直放上去后，直到整个数组都分完合完后，也就是整个数组有序的时候。
这样的做法是二分归并。 还有K分归并，就是有K个数组，把这K个数组合并成一个有序数组。主要就是用分治的思想，也就是先2个2个合并（不交叉的2项：比如就是1和2合并，3和4合并。不是1和2合并成整体再和3合并，进而再和4合并，这样就很慢…）。 - 代码
public static void mergeSortMain(int[] arr) {
if(arr == null || arr.length < 1) {
return;
}
mergeSort(arr, 0, arr.length-1);
}
public static void mergeSort(int[] arr, int left, int right) {
if(left >= right) {
return ;
}
int mid = left + (right-left)/2 ;
mergeSort(arr, left, mid);
mergeSort(arr, mid+1, right);
merge(arr, left, mid, right);
}
public static void merge(int[] arr, int left, int mid, int right) {
int[] help = new int[right-left+1];
int index = 0;
int i = left;
int j = mid+1;
while(i <= mid && j <= right) {
help[index++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
}
while(i <= mid) {
help[index++] = arr[i++];
}
while(j <= right) {
help[index++] = arr[j++];
}
for(int k = 0; k < help.length; k++) {
arr[left+k] = help[k];
}
}
- 稳定性 ： 可以做到稳定性，就是在合并的过程中，如果遇到相等的，就先放最前面的那个数字就可以了。
有个小拓展：空间复杂度可以达到O(1)，但是很难，有兴趣的可以去搜索“归并排序，内部缓存法”资料。 - 小应用：小和问题 和 逆序对问题。
堆排序
- 时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 主要思想： 就是把数组建立成一个堆（大根堆或小根堆都可以），然后在依次取出堆顶元素的顺序就是 排好序 的数组元素顺序了。 如果只是一个建堆的过程，那么时间复杂度只是O(N)。
对于堆和数组来说，其下标关系：
左孩子是 （index2+1）。右孩子是（index2+2）。
父亲节点是（index-1）/ 2。 - 代码
public static void heapSort(int[] arr) {
if(arr == null || arr.length < 1) {
return;
}
for(int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
int size = arr.length; // 用size来维护这个堆的大小，从而在数组中实现排序
swap(arr, 0, --size);
while(size > 0) {
heapify(arr, 0, size);
swap(arr, 0, --size);
}
}
// 将arr[index] 的元素 放入堆中， 并使其还是一个堆 （shift_up操作）
public static void heapInsert(int[] arr, int index ) {
while( arr[(index-1)/2 ] < arr[index] ) {
swap(arr, (index-1)/2, index);
index = (index-1) / 2;
}
}
// 对堆中的位置为index的元素进行 shift_down操作， 使其满足一个大小为size的堆
public static void heapify(int[] arr, int index, int size) {
int left = index*2 + 1;
while(left < size) {
// largest 存储的是下标
int largest = left+1 < size && arr[left+1] > arr[left] ? left+1 : left;
largest = arr[index] >= arr[largest] ? index : largest;
if(largest == index) {
break;
}
swap(arr, index, largest);
index = largest;
left = index*2 + 1;
}
}
// 对arr[a], arr[b] 这两个数进行交换
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
- 稳定性： 做不到稳定性。
- 小应用： 在流动的数据中快速找到中位数，以及有关优先队列的各种问题。
华为工作强度 839人发布