比较排序
冒泡排序
外层循环每一次经过两两比较，把每一轮未排定部分最大的元素放到了数组的末尾
- 时间复杂度：
- 空间复杂度：
是否稳定：稳定
public int[] bubbleSort(int[] nums){int len = nums.length;//循环的次数，跟数组下标无关，也就是冒多少轮泡，数组就有序了，显然是len-1次即可for (int i = 0; i < len - 1; ++i){//每轮冒泡都会定义一个最终位置，因此每轮需要比较的次数为len-1-ifor (int j = 0; j < len - i - 1; ++j){if ( nums[j] > nums[j+1])swap(nums, j, j+1);}}return nums;}
选择排序
每一轮选取未排定的部分中最小的部分交换到未排定部分的最开头，经过若干个步骤，就能排定整个数组。即：先选出最小的，再选出第 2 小的，以此类推
时间复杂度：
- 空间复杂度：
- 是否稳定：数组实现的选择排序不稳定，链表是稳定的
优点：交换次数最少
public int[] selectionSort(int[] nums){ int len = nums.length; //循环不变量：[0, i) 之间的元素是有序的，且是最终顺序 for (int i = 0; i < len - 1; ++i){ //暂存当前元素的索引作为最小元素 int minIndex = i; //选择区间[i, len-1]里最小元素的索引，交换到下标i for (int j = i+1; j < len; ++j){ if ( nums[j] < nums[minIndex]) minIndex = j; } swap(nums, i, minIndex); } return nums; }插入排序
每次将一个数字插入一个有序的数组里，成为一个长度更长的有序数组，有限次操作以后，数组整体有序
时间复杂度：
- 空间复杂度：
- 是否稳定：稳定
优点：数组「几乎有序」的前提下表现良好，因为内层循环
nums[j-1] > temp条件基本不满足public int[] sort(int[] nums){ int len = nums.length; //循环不变量：将nums[i]插入[0, i)后变为有序数组 for (int i = 1; i < len; ++i){ int j = i; int temp = nums[j]; //暂存当前元素，作为本轮插入的元素 //将之前比他大的元素逐个后移，直到找到插入位置 while ( j > 0 && nums[j-1] > temp){ //这里的判断条件容易出错，我们是要为temp找到插入位置 nums[j] = nums[j-1]; j--; } nums[j] = temp; } return nums; }希尔排序—插入排序进阶版—缩小增量排序
插入排序的优化。在插入排序里，如果靠后的数字较小，它来到前面就得交换多次。「希尔排序」改进了这种做法。带间隔地使用插入排序，直到最后「间隔」为 1 的时候，就是标准的「插入排序」，此时数组里的元素已经「几乎有序」了，这个间隔就叫增量
时间复杂度：取决于增量序列
- Shell增量 {1,2,4,8,…} 这种序列并不是很好的增量序列，使用这个增量序列的时间复杂度（最坏情形）是
- Hibbard增量 {1,3,7, … ,2^k-1} ，这种序列的时间复杂度(最坏情形)为
- Sedgewick增量 {1,5,19,41,109, ……}，这种序列的时间复杂度(最坏情形)为
- Shell增量 {1,2,4,8,…} 这种序列并不是很好的增量序列，使用这个增量序列的时间复杂度（最坏情形）是
- 是否稳定：不稳定
public static void shellSort(int[] nums){
int len = nums.length;
//增量gap，并逐步缩小增量，可以根据数组长度重新设计增量
for (int gap = len/2; gap > 0; gap /= 2){
//原数组被分成了gap组，每组len/gap个数据
for (int i = gap; i < len; ++i){
int j = i;
int temp = nums[j]; //暂存元素，在该组中将比他大的元素后移，直到找到插入位置
while (j >= gap && nums[j-gap] > temp){ //主要看j-gap能否取到
nums[j] = nums[j-gap];
j -= gap;
}
nums[j] = temp;
}
}
}
归并排序
先分，然后借助额外空间，合并两个有序数组，得到更长的有序数组
- 时间复杂度：
- 空间复杂度：
辅助数组所占空间 - 是否稳定：稳定
public class MergeSort {
public static void main(String[] args) {
int[] nums = {2,3,9,5,7,8,4,5};
int[] temp = new int[nums.length];
mergeSort(nums,0,nums.length-1,temp);
System.out.println(Arrays.toString(nums));
}
/**
* 分解数组+调用合并方法合并数组
* @param nums 待排序数组
* @param left 待排序数组的起始索引
* @param right 待排序数组的结束索引
* @param temp 全局临时数组
*/
public static void mergeSort(int[] nums, int left, int right, int[] temp){
if (left == right) return; //递归终止条件，只有一个元素的时候，是有序的，直接返回
int mid = left + (right - left >> 1); //计算出中间位置
mergeSort(nums, left, mid, temp); //将数组分成两半进行排序
mergeSort(nums, mid+1, right, temp);
//将分成的两部分有序数组进行合并
merge(nums, left, mid, right, temp);
}
/**
* 合并两个有序数组 nums[left:mid] nums[mid+1:right] 到新数组 temp
*/
public static void merge(int[] nums, int left, int mid, int right, int[] temp){
int i = left; //初始化i，左边有序序列的初始索引
int j = mid + 1; //初始化j，右边有序序列的初始索引
int t = 0; //初始化t，指向temp数组的当前索引
//1、先把左右两边（有序）的数据，按有序规则填充到temp数组，即谁小谁填充
//直到左右两边的有序序列，有一边处理完毕为止
while( i <= mid && j <= right){
if (nums[i] <= nums[j]){ //这里如果不加等号就失去了稳定性，原来靠前的元素不一定靠前了
temp[t++] = nums[i++];
}else{
temp[t++] = nums[j++];
}
}
//2、把有剩余元素的序列的剩余元素依次全部填充到temp
while( i <= mid ) temp[t++] = nums[i++];
while( j <= right) temp[t++] = nums[j++];
//3、将临时数组temp的元素拷贝回原数组
//注意，并不是每次拷贝都拷贝所有元素
int tempLeft = 0;
int numsLeft = left;
while (numsLeft <= right) {
nums[numsLeft++] = temp[tempLeft++];
}
}
}
快速排序
快速排序是选取一个“哨兵”(pivot)，将小于pivot放在左边，把大于pivot放在右边，分割成两部分，并且可以固定pivot在数组的位置，在对左右两部分递归进行排序
快速排序的递归终止条件是**left >= right**
- 时间复杂度：
- 空间复杂度：
主要来自于递归函数的栈空间 - 是否稳定：不稳定
//最基础写法
public static void quickSort(int[] nums, int left, int right){
if ( left >= right) return;
int i = left;
int j = right;
int pivot = nums[left];
while(i < j){
while ( i < j && nums[j] >= pivot) j--;
while ( i < j && nums[i] <= pivot) i++;
swap(nums, i, j);
}//结束时l==r
swap(nums, i, left); //pivot与i==j的位置交换
quickSort(nums, left, i-1);
quickSort(nums, j+1, right);
}
//将上面的方法拆分出一个partition方法
public static void quickSort(int[] nums, int left, int right){
if (left >= right)
return ;
int i = partition(nums, left, right);
quickSort(nums, left, i-1);
quickSort(nums, i+1, right);
}
private static int partition(int[] nums, int left, int right) {
int i = left;
int j = right;
int pivot = nums[left];
while(i < j){
while ( i < j && nums[j] >= pivot) j--;
while ( i < j && nums[i] <= pivot) i++;
swap(nums, i, j);
}//结束时l==r
swap(nums, i, left); //pivot与i==j的位置交换
return i;
}
优化最差时间复杂度，
—>
—-随机选取哨兵pivot- 同样地，由于快速排序每轮选取「子数组最左元素」作为「基准数」，因此在输入数组 完全有序 或 完全倒序 时， partition() 每轮只划分一个元素，达到最差时间复杂度 O(N^2)
因此，可使用 随机函数 ，每轮在子数组中随机选择一个元素作为基准数，这样就可以极大概率避免以上劣化情况。值得注意的是，由于仍然可能出现最差情况，因此快速排序的最差时间复杂度仍为O(N^2)
public static void quickSort(int[] nums, int left, int right){ if (left >= right) //这里不加大于会错 return ; int i = partition(nums, left, right); quickSort(nums, left, i-1); quickSort(nums, i+1, right); } private static int partition(int[] nums, int left, int right) { //在闭区间 [left, right] 随机选取任意索引，并与 nums[left] 交换 int random = (int)(left + Math.random() * (right - left + 1)); swap(nums, left, random); int i = left; int j = right; int pivot = nums[left]; while(i < j){ while ( i < j && nums[j] >= pivot) j--; //这里不加等号会错 while ( i < j && nums[i] <= pivot) i++; swap(nums, i, j); }//结束时l==r swap(nums, i, left); //pivot与i==j的位置交换 return i; }
优化最差空间复杂度，
—>
—-tail call- 由于普通快速排序每轮选取「子数组最左元素」作为「基准数」，因此在输入数组 完全倒序 时， partition() 的递归深度会达到 NN ，即 最差空间复杂度 为 O(N)
每轮递归时，仅对 较短的子数组 执行哨兵划分 partition() ，就可将最差的递归深度控制在 O(log N)（每轮递归的子数组长度都 ≤ 当前数组长度），即实现最差空间复杂度O(logN)
public static void quickSort(int[] nums, int left, int right){ while ( left < right ){ //使用i将整个数组划分为两部分 int i = partition(nums, left, right); //仅递归至较短的子数组 if (i - left < right - i){ //左边的子数组短 quickSort(nums, left, i - 1); left = i + 1; }else { //右边的子数组短 quickSort(nums, i + 1, right); right = i - 1; } } } private static int partition(int[] nums, int left, int right) { int i = left; int j = right; int pivot = nums[left]; while(i < j){ while ( i < j && nums[j] >= pivot) j--; while ( i < j && nums[i] <= pivot) i++; swap(nums, i, j); }//结束时l==r swap(nums, i, left); //pivot与i==j的位置交换 return i; }堆排序
堆排序是选择排序的优化，选择排序需要在未排定的部分里通过「打擂台」的方式选出最大的元素（复杂度 O(N)），而「堆排序」就把未排定的部分构建成一个「堆」，这样就能以O(logN) 的方式选出最大元素。
步骤：
- 将无序序列构建成一个堆，升序—大顶堆，降序—小顶堆
- 从最后一个非叶子结点开始，即从
i = length/2 - 1开始，逐步往上调整堆 - 当前节点分别于左右子结点对比，如果有子结点比当前结点大，那么当前结点下沉，下沉到没有子结点比他大
- 是因为我们从下往上调整，当前结点可能比右结点小，但是不能只下沉一层，因为当前结点还可能比右结点的右结点还小，因此得有个循环，判断下沉到哪里，并用指针跟进，下沉到，没有子结点比他还小了，最后使用该指针把原来的当前结点的值赋给他
- 调整完当前结点，
i--，继续调整，直到i >= 0不满足，调整到根结点，整个数组被调整为一个大顶堆
- 从最后一个非叶子结点开始，即从
- 将堆顶元素与数组末尾元素交换，将最大元素沉到数组末端
- 重新调整剩余的结构，使其满足大顶堆的定义，然后继续交换堆顶元素与当前末尾元素（数组长度是递减的），反复执行交换调整操作
- 将无序序列构建成一个堆，升序—大顶堆，降序—小顶堆
- 时间复杂度：
- 空间复杂度：
是否稳定：不稳定
public static void heapSort(int[] nums){ //将整个数组调整为大顶推，这个过程中length是不变的 for (int i = nums.length/2 - 1; i >= 0; --i){ adjustHeap(nums, i, nums.length); } //根据大顶堆进行排序 for (int j = nums.length - 1; j >= 0; --j){ //堆顶元素即为当前最大元素，交换一下放到末尾，此时数组长度变为length-1 swap(nums, 0, j); //因为调整上来的数肯定不是最大，所以需要下沉，因为剩下的都是有序的，只下沉这一次即可 adjustHeap(nums, 0, j); //这里应该用j，不能用len-1，因为变化的 } } /** * 将数组部分元素（该部分元素构成了以i为非叶子节点的树）调整为大顶堆 * @param nums 待排序数组 * @param i 非叶子结点在数组中的索引 * @param length 对多少个元素进行调整，因为调整过程中会不断减少 */ public static void adjustHeap(int[] nums, int i, int length){ int temp = nums[i]; for (int k = 2 * i + 1; k < length; k = k * 2 + 1){ if ( k + 1 < length && nums[k] < nums[k+1] ){ k = k + 1; } if ( nums[k] > temp ){ nums[i] = nums[k]; i = k; }else { break; } } nums[i] = temp; }非比较排序
计数排序
计数排序是典型的空间换时间算法，开辟额外数据空间存储用索引号记录数组的值和数组值个数
- 找出待排序的数组的最大值和最小值
- 统计数组值的个数
- 反向填充目标数组
- 时间复杂度：
- 空间复杂度：适用于数组量大但是范围小，这样空间复杂度就回比较小
是否稳定：稳定/不稳定
public static void countingSort(int[] nums){ int min = Arrays.stream(nums).min().getAsInt(); //速度挺慢的 int max = Arrays.stream(nums).max().getAsInt(); int[] count = new int[max - min + 1]; //max-min+1 for (int num : nums){ count[num - min] ++; //min可能为负但是数组下标不能为负 } for (int i =0, j = 0; i < count.length; ++i){ while ( count[i]-- > 0){ nums[j++] = i + min; //减去的再加上来 } } }基数排序
将所有待比较的数值统一为同样的数位长度，数位较短的数前面补零。然后从最低为开始，一次进行一次排序，这样从最低位排序一直到最高位排序拍完后，数列就变成一个有序序列
第一轮排序
- 将每个元素个位数取出，然后看这个数应该放在哪个对应的桶（一个一维数组）
- 按照这个桶的顺序（即一维数组的下标）取出数据，放回原数组
第二轮排序
求数组最大值最小值，人为设置桶的数量，然后可以获得每个桶能装的数据范围
- 遍历数组元素，看属于哪个桶，在桶内再进行排序
若有收获，就点个赞吧
0 人点赞
