快速排序
步骤
- 从列表选出一个基准值 pivot
- 重新排列数组，所有比基准值小的放在基准值左边，所有比基准值大的放在基准值右边。
- 递归把基准值左右两边的数列排序。
时间复杂度O(nlogn)
最坏的情况：序列已经是升序排序，需要比较n(n-1)/2次，为O(n^2)
最好的情况：每次划分都是正好两半 T(n) <= 2T(n/2)+O(n) —> T(n) = O(nlogn)
空间复杂度O(nlogn)：由于是递归调用，空间复杂度为O(nlogn)
快速排序是不稳定的，时间复杂度O(nlogn)，不稳定发生在中枢元素和a[j]，中枢元素左边的元素可能和右边的元素相等，当中枢元素和其交换时，破坏了稳定性
public static void quickSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int pivot = partition(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[low];
while (low < high) {
while (low < high && arr[high] >= pivot)
high--;
arr[low] = arr[high];
while (low < high && arr[low] <= pivot)
low++;
arr[high] = arr[low];
}
arr[low] = pivot;
return low;
}
冒泡排序
相邻两个元素进行交换，把大的元素浮到最上面
时间复杂度O(n^2)：最外层for执行n次，内层循环j从0～i-1，i从n-1～1，复杂度为n*(n-1)/2，
空间复杂度O(1)：只需要一个temp位置交换
稳定：比较两个相邻元素并进行交换，如果相等，则不会交换，稳定性没有被破坏。
public 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-i-1;j++) {
if (arr[j]>arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
选择排序
一次排序后把最小的元素放在最前面
时间复杂度O(n^2)：比较次数和初始状态无关，为n(n-1)/2，最好，最坏和平均情况均为O(n2)
空间复杂度O(1)：
不稳定，不稳定发生在最小的元素当前元素交换时，如果当前元素在最小元素前面，并且比和当前元素相等时，交换之后稳定性就被破坏
public static void selectSort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
int minIndex = 0;
for(int i=0;i<arr.length-1;i++) {//比较n-1次
minIndex = I;
for (int j = i+1; j < arr.length; j++) {//从i+1开始比较，minIndex默认为I
if (arr[j]<arr[minIndex]) {
minIndex = j;
}
}
if (minIndex!=i) {
swap(arr, i, minIndex);//minIndex不为i，说明找到更小的，交换
}
}
}
插入排序
在一个已经排好序的序列中，为下一个找到一个合适的插入位置
时间复杂度O(n^2)：外层for共执行arr.length-2次，内层循环最少执行1次，最多执行index次，算法复杂度n*(n-1)/2
空间复杂度O(1)：只需要一个位置key用于交换
稳定：插入排序是在已经有序的小序列中进行插入一个元素，即使遇到相等的元素，也是插入在其后面，稳定性没有被破坏
public static void insertSort(int[] arr) {
if (arr == null || arr.length == 0)
return;
for (int i = 1; i < arr.length; i++) {// 假设第一个位置正确，要往后移，必须假设第一个
int j = I;
int target = arr[i];// 待插入
while (j > 0 && target < arr[j - 1]) {// 往后移
arr[j] = arr[j - 1];
j--;
}
arr[j] = target;
}
}
希尔排序
思想：分组插入排序，将整个待排序序列分割成若干个子序列，并分别进行插入排序，然后再缩小增量继续排序，当增量足够小时，再对全体元素进行直接插入排序。
时间复杂度O(nlogn)：
时间复杂度依赖于增量序列
最好的情况：序列是升序序列，需要比较n次，后移赋值操作为0次，O(n)
最坏的情况：序列的降序序列，O(nlogn)
空间复杂度O(1)：只需要一个位置置换
public static void shellSort(int[] arr) {
int i, j, gap;
for (gap = arr.length / 2; gap > 0; gap /= 2) {
for (i = gap; i < arr.length; i++) {
for (j = i - gap; j >= 0 && arr[j] > arr[j + gap]; j -= gap)
swap(arr, j, j + gap);
}
}
}
归并排序
合并两个有序的子数组
思想：递归分治+归并
把待排序列看成两个有序序列，然后合并两个子序列。倒着看，两两合并，四四合并。。。最终形成有序序列。
时间复杂度O(nlogn)：归并排序是一种非“就地”排序，需要和待排序序列一样多的辅助空间，故归并排序的缺点是所需额外空间多，对长度为n的数组，需要进行logn趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论在最好还是最坏情况下都是O(nlogn)
空间复杂度O(n)：排序时需要和待排序序列一样的空间，空间复杂度为O(n)
稳定：归并排序是把序列递归的分成短序列，递归出口是只有一个元素或者2个元素短有序序列，然后把各个有序序列合并成有序的长序列，不断合并知道原序列全部排好序。在短序列中，即使两个元素相等也不会交换，因此稳定性没有被破坏。
使用场合
public static void mergeArray(int[] arr, int left, int mid, int right) {
if (arr == null || arr.length == 0)
return;
int[] temp = new int[right-left+1];
int i = left, j = mid + 1;
int k = 0;
// 二路归并
while (i < mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
// 处理子数组中剩余元素
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
// 从临时数组中拷贝到目标数组
for (i = 0; i < temp.length; i++) {
arr[left + i] = temp[I];
}
}
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
// 归并排序使得左边序列有序
mergeSort(arr, left, mid);
// 归并排序使得右边序列有序
mergeSort(arr, mid + 1, right);
// 合并两个有序序列
mergeArray(arr, left, mid, right);
}
}
堆排序
时间复杂度O(nlogn)：最好，最坏，平均均为O(nlogn)
空间复杂度O(1)
思想：
堆（二叉堆）：一棵完全二叉树
- 最大堆调整：将堆末端子节点作调整，使得子节点永远小于父节点
- 创建最大堆：将堆所有数据重新排序，使其成为最大堆
- 堆排序：移除位于第一个数据的根节点，并作最大堆调整堆递归运算，将最大的元素从堆中分离
parent(i) = floor((i-1)/2)，i的父节点下标
left(i) = 2i+1，i的左子节点下标
right(i) = 2(i+1)，i的右子节点下标
不稳定：堆和其子节点（堆，左节点，右节点）交换不会破坏稳定性，堆顶元素移除时，父节点和某个元素交换，刚好该元素后面有相同的元素，就会破坏稳定性。
public static void heapSort(int[] arr) {
int len = arr.length - 1;
int beginIndex = (len - 1) / 2;// 第一个非叶子节点
// 将数组堆化
for (int i = beginIndex; i >= 0; i--) {
maxHeapify(arr, i, len);
}
// 对堆化数组排序，每次都移出最顶层节点arr[0]，与尾部节点位置调换，同时遍历长度-1，
// 然后从新调整被换到根节点末尾都元素，使其符合堆堆特性，直至未排序堆堆长度未0
for (int j = len; j >= 0; j--) {
swap(arr, 0, j);
maxHeapify(arr, 0, j - 1);
}
}
private static void maxHeapify(int[] arr, int index, int len) {
int li = (index * 2) + 1;// 左子节点索引
int ri = 2 * (index + 1);// 右子节点索引
int cMax = li;// 子节点值最大索引，默认左子节点
if (li > len)
return;// 左子节点索引超出计算范围，直接返回
if (ri <= len && arr[ri] > arr[li])
cMax = ri;// 先判断左右子节点哪个大
if (arr[cMax] > arr[index]) {
swap(arr, cMax, index);// 如果父节点被子节点调换
maxHeapify(arr, cMax, len);// 则需要继续判断换下后堆父节点是否符合堆堆性质
}
}
不稳定排序：选择排序，快速排序，希尔排序，堆排序
稳定排序：冒泡排序，插入排序，归并排序，基数排序
