- 基本排序：插入，选择，冒泡
- 三大排序：归并，快速，堆排
1、归并排序 -- 时间复杂度O(N*logN)，空间复杂度O(N)
思路：递归方法，本质是压栈出栈的过程，关键点是找出递归的basecase，即问题划分到不能再往下划分的点，再将排好序的两部分合并即可
// 非递归方法，每相邻2个数排序，再下一层排序，k值每次*2,即可
public class MergeSort(){
public static void mergeSort(int[] arr){
if(arr == null || arr.length<2){
return;
}
mergeSort(arr, 0, arr.length-1);
}
public static void mergeSort(int[] arr, int left, int right){
int mid = left + ((right-1)>>1)
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[] tmp = new int[right-left+1];
int i = 0;
int p1 = left;
int right = mid + 1;
while(p1<=mid && p2<=right){
tmp[i++] = arr[p1] < arr[p2] : arr[p1++] ? arr[p2++];
}
while(p1<=mid){
tmp[i++] = arr[p1++];
}
while(p2<=right){
tmp[i++] = arr[p2++];
}
for(i=0; i<tmp.lenth; i++){
arr[left+i] = tmp[i];
}
}
}
时间复杂度：T(N) = T(N/2) + T(N/2) + O(N)，可利用master公式得到N*logN
2、快速排序 -- 时间复杂度O(N*logN)，空间复杂度O(logN)
思路：先设定一个小于区，对于每一个从左到右的数，与最后的值比较，若小于比较值，则小于区域左移一位，即将此位的数值与小于区右边的值交换，若大于比较值则不变。如0 3 6 7 5 4，比较值为4，小于区域在0左边，从0开始区域右移，到3右移，到7比比较值大，则不变，到5不变，到4时将4与比较区的右侧值6与4交换，此时划分为0 3 4和6 7 5两部分。
public class QuickSort(){
public static int[] partition(int[] arr, int left, int right){
int less = left - 1;
int more = right;
while(left < more){
if(arr[left] < arr[right]){
swap(arr, ++less, left++);
}
else if(arr[left] > arr[right]){
swap(arr, --more, left);
}
}
swap(arr, more, right);
// 返回等于区域边界的位置
return new int[] {less+1, more};
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void quickSort(int[] arr, int left, int right){
if(left < right){
// 随机选择一个数与最后的数交换,作为比较值,可使得随机快速排序的时间复杂度随机期望为NlogN
swap(arr, left+(int)(Math.random()*(right-left+1)), right);
// 利用荷兰国旗思路，将小的放到左边，大的放到右边，相等的在中间，并返回相等部分的位置
int[] p = partition(arr, left, right);
// 递归思想,p[0]-1为左侧区域的右边界
quickSort(arr, left, p[0]-1);
// p[1]+1是右侧区域的左边界
quickSort(arr, p[1]+1, right);
}
}
}
3、堆排序 -- 时间复杂度O(N*logN)，空间复杂度O(1)
思路：二叉树，建立大根堆，然后将最大值排除，堆大小减小，再从上到下找到此时堆的最大值，继续排序，继续减小堆
public class HeapSort(){
public static void heapSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
for(int i=0; i<arr.length; i++){
heapInsert(arr, i);
}
// 定义堆的大小,以此来控制需要排序数值的长度
int heapSize = arr.length;
// 将第一个数与最后一个数交换,同时堆的大小减1
swap(arr, 0, --heapSize);
while(heapSize > 0){
heapify(arr, 0, heapSize);
swap(arr, 0, --heapSize);
}
}
// 构建大根堆的过程,此时是虽然每颗子树的最大值为头节点,但整体是无序的,知道全局最大值
public static void heapInsert(int[] arr, int index){
// 当自节点的数值大于其父节点时,交换位置
while(arr[index] > arr[index-1]/2){
swap(arr, index, (index-1)/2);
// 同时判断交换后的节点的父节点,依次向上
index = (index-1)/2;
}
}
public static void heapify(int[] arr, int index, int heapSize){
// 左孩子
int left = index * 2 + 1;
while(left < heapSize){
// 当满足左下标小于size时,返回数值较大的孩子的下标
int largest = left+1<heapSize && arr[left+1]>arr[left] ? left+1 : left;
// 再与父节点的值比较,返回父节点及子节点中最大值的下标
largest = arr[largest]>arr[index] ? largest : index;
// 如果当前最大值为父节点, 则退出循环
if(largest == index){
break;
}
// 如果不是则将最大值与父节点交换, 同时将父节点置为最大节点的索引, 继续循环
swap(arr, largest, index);
index = largest;
// 继续得到此时父节点的左孩子
left = index * 2 + 1;
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
4、冒泡排序 -- 时间复杂度O(N^2)，空间复杂度1
思路：从左到右互换逆序的相邻元素，一轮互换后，最大的值位于最右侧，遍历N个数，二轮遍历N-1个数...因此复杂度为N^2
public class BubbleSort(){
public static void bubbleSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
// 每次从左向右遍历end个元素，互换相邻元素，每一轮过后，最大值将被排在最右侧
for(int end=arr.length-1; end>0; end--){
for(int i=0; i<end; i++){
if(arr[i]>arr[i+1]){
swap(arr, i, i+1);
}
}
}
}
public static void swap(int[] arr, int i, int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
5、插入排序 -- 时间复杂度O(N^2)，空间复杂度1
思路：针对某一个位置i，其前面的数值均已排好序，将i插入到前面对应的位置，类似于抓到扑克牌后，将牌插入的过程
public class QuickSort(){
public static void insertSort(){
if(arr == null || arr.length < 2){
return;
}
// 从第1个位置开始, 此时与第0位置的数相比
for(int i=1; i<arr.length; i++){
// 每次对要插入的i位置, 看前面的j-1位置与j位置的大小, 若逆序则互换
for(int j=i-1; j>=0 && arr[j]>arr[j+1]; j--){
swap(arr, j, j + 1);
}
}
}
public static void swap(int[] arr, int i, int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
6、选择排序 -- 时间复杂度O(N^2)，空间复杂度1
思路：从数组中选择最小元素，将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置
public static void selectionSort(int[] arr){
if (arr == null || arr.length < 2){
return;
}
for(int i=0; i<arr.length; i++){
int minIndex = i;
for(int j=i+1; j<arr.length; j++){
minIndex = arr[j]<arr[minIndex] ? j : minIndex;
}
swap(arr, i, minIndex);
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
7、桶排序
思路：
代码：
8、排序在系统中的实现
例如在java中，Arrays.sort()是用来排序的函数，当size小于60时使用插入排序，在大于60时，如果是基本数据类型使用快速排序，如果是自己定义的数据类型，使用归并排序；原因是稳定性问题，快速排序是不稳定的，对于基本数据类型而言，不是很关心稳定性问题，而mergesort是稳定的，对自己定义的数据类型，排序的稳定性就很重要了，关系到一些逻辑的处理。
