【排序算法】
比较排序
七大排序算法
❤️稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的
插入排序
⭕️插入排序的思想：从第二个元素开始往后遍历，遍历到每个元素都把该元素插入该元素之前的序列中，并保持序列有序性。
比如将第二个元素插入第二个元素之前的序列并保持有序性，然后把第三个元素插入第三个元素之前的序列，并保持有序性，到此前三个元素已经有序，然后把第四个插入前三个元素，并保持有序性，依次类推，直到所有元素都有序。
//插入排序（由小到大）
//时间复杂度：O(N*N) 空间复杂度：O(1)
public static void insertSort(int[] arr){
for (int i = 1; i < arr.length; i++) {
int j = 0;
int cur = arr[i];
for (j = i - 1; j >=0; j--) {
if (cur < arr[j]){
arr[j+1] = arr[j];
}else {
arr[j+1] = cur;
break;
}
}
if(j == -1){
arr[0] = cur;
}
}
}
希尔排序
⭕️希尔排序的思想：希尔排序是插入插入排序的优化算法。希尔排序是先取一个整数gap，意思是将整个序列分为gap组（下面的图会演示具体是怎么分组的），然后针对每个组进行插入排序，这一趟下来，序列就会稍微有序点，然后gap/=2，然后再针对每个组进行插入排序，然后序列就会更有序点。然后gap/=2，再进行下一轮。直到gap==1，然后再对序列整体来个插入排序（这次就不分组了）
⭕️当gap>1时都是预排序，预排序的目的是让序列变得更有序，只有最后一次gap==1时这次的插入排序才能让序列真正的有序。如果不分组排序，直接一上来就插入排序，当数据量比较大时，比较次数就会很多。分组就能减少比较次数。
⭕️希尔排序又称为缩小增量排序，gap就是那个增量。希尔排序的时间复杂度并不好计算，因为增量的取值不确定。资料上显示的时间复杂度是：O(N1.25)到O(1.6*N1.25)
private void shell(int[] arr, int gap){
for (int i = gap; i < arr.length; i++) {
int cur = arr[i];
int j = 0;
for (j = i - gap; j >= 0 ; j -= gap) {
if (cur < arr[j]){
arr[j+gap] = arr[j];
}else {
break;
}
}
arr[j+gap] = cur;
}
}
//希尔排序
public void shellSort(int[] arr){
int gap = arr.length;
while (gap > 1){
shell(arr, gap);
gap/=2;
}
shell(arr,1);
}
选择排序
⭕️选择排序的思想：每次选取未排序序列中最小值放到最前面，第一次选最小值放到0下标处，第二次选剩余序列中最小值放到1下标处，第三次选剩余序列中最小值放到2下标处。依次往后遍历。
public static void swap(int[] arr,int index1,int index2){
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}
//选择排序，选择排序不管数据是有序还是无序，都要比较这么多次。所以该算法比较慢
//时间复杂度：O(N*N) 空间复杂度：O(1)
public static void selectSort(int[] arr){
for (int i = 0; i < arr.length; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if(arr[j] < arr[minIndex]){
minIndex = j;
}
}
swap(arr,minIndex,i);
}
}
时间复杂度：O(N * N)，空间复杂度: O(1)
堆排序
⭕️堆排序思想：比如要排成递增序列，要先将无序序列建成一个大根堆，然后第一次取堆顶元素和最后一个元素交换，然后再调整为大根堆（调整的范围不包括已经交换下来的元素），第二次取堆顶元素和倒数第二个元素交换，然后再调整为大根堆（调整的范围不包括已经交换下来的元素）
⭕️第一次交换放到最后位置是最大的元素，第二次交换放到倒数第二位置的是第二大元素，第三次交换放到倒数第三位置的是第三大元素，依次类推，就可以排序
🔑总共两个大步骤：建堆，交换和向下调整
/**
*
* @param arr:向下调整的堆
* @param root 向下调整的子树的根节点
* @param len 调整的界限（调整的数据下标<len）
*/
public static void shiftDown(int[] arr,int root,int len){
int parent = root;
int child = root*2+1; //左孩子
while(child < len){
//让child指向最大的孩子节点
if(child + 1 < len && arr[child+1] > arr[child]){
child++;
}
//孩子比父亲大就交换
if(arr[child] > arr[parent]){
swap(arr,child,parent);
parent = child;
child = parent * 2 + 1;
}else{
break;
}
}
}
//堆排序
public static void heapSort(int[] arr){
//建大根堆
for (int i = (arr.length-2)/2; i >=0 ; i--) {
shiftDown(arr,i,arr.length);
}
//排序
int end = arr.length - 1;
while (end >= 0){
swap(arr,end,0);
shiftDown(arr,0,end);
end--;
}
}
堆排序时间复杂度：O(N*logN) 空间复杂度：O(1)
🔑==堆排序时间复杂度分析：==堆排序有两大步骤，建堆和操作堆。建堆之前在堆那一节已经分析过了，时间复杂度是：O(N)。下面主要来分析操作堆：
以满二叉树来分析：最下一层元素交换到堆顶之后的向下调整次数：h-1(最坏情况下是h-1，h是树的高度)，倒数第二层是：h-2，倒数第三层是h-3，第一层是：0
S=(2 ^ 0 * 0) + (2 ^ 1 * 1) + (2 ^ 2 * 2) + (2 ^ 3 * 3) +…+ (2 ^ h-2 * (h-2)) + (2 ^ h-1 * (h-1))
2S=(2 ^ 1 * 0) + (2 ^ 2 * 1) + (2 ^ 3 * 2) + (2 ^ 4 * 3) +…+ (2 ^ h-1 * (h-2)) + (2 ^ h * (h-1))
相减得：- (2 ^ 1+ 2 ^ 2 + 2 ^ 3 + 2 ^ h-1)+ (2 ^ h * (h-1)-0 ，化简后可得时间复杂度是O(n*logn-2n)，上面建堆是O(N)，相加得O(N * logN-N)，再化简得O(N * logN)
冒泡排序
⭕️==冒泡排序思想：==每次遍历将当前序列中最大值交换至最右侧，第一次遍历将前n个元素中最大值交换至最右侧，第二次将前n-1个元素中最大值交换至右侧第二个位置，第三次将前n-2个元素中最大值交换至右侧第三个位置。循环遍历n-1次即可将序列排序。
public static void swap(int[] arr,int index1,int index2){
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}
public static void bubbleSort(int[] arr){
for (int i = 0; i < arr.length - 1; i++) {
boolean flg = false;
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j+1]){
flg = true;
swap(arr,j,j+1);
}
}
if (!flg){
return;
}
}
}
🔑时间复杂度：O(N * N)，空间复杂度：O(1)
快速排序
⭕️快速排序是采用分治的思想，使用递归的方式来排序，快排的思想：先从当前序列中选取一个基准，然后把比基准小的数字放到基准左面，比基准大的数字放到基准右面。然后再分别对分出的左右序列采取相同的思想。
根据基准划分左右序列的算法以下两种都可以：
private static void insert1Sort(int[] arr,int left,int right){
for (int i = left + 1; i <= right; i++) {
int cur = arr[i];
int j = i - 1;
while(j >= left && arr[j] > cur){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = cur;
}
}
private static void quick(int[] arr,int left,int right){
if(left >= right){
return;
}
//当递归n次之后，如果当前要排序的区间比较小，就无需再接着递归下去了，因为每次递归下去，区间都会趋于有序（），这时可以使用插入排序（因为插入排序越有序越快）。
if(right - left <= 500){
insert1Sort(arr,left,right);
return;
}
//使基准左侧数字都小于基准，基准右侧数字都大于基准，然后返回基准的下标
int index = test1(arr,left,right);
//排序左半个数组
quick(arr,left,index - 1);
//排序右半个数组
quick(arr,index + 1,right);
}
public static void quickSort(int[] arr){
quick(arr,0,arr.length - 1);
}
🔑Hoare法，思想：左指针从左边开始往右找到大于基准的元素，右指针从右边开始找到小于基准的元素，然后交换，然后左指针再向右找，右指针再向左找，都找到后交换，直到左指针和右指针相遇。
//Hoare法，返回分割后的数组的基准下标
private static int test(int[] arr, int left, int right) {
//定义cur为基准数字 ，基准取当前[left,right]区间的第一个数字
int cur = arr[left];
int first = left;
while(left < right){
while (left < right){
if (arr[left] > cur){
break;
}
left++;
}
while (left < right){
if (arr[right] < cur){
break;
}
right--;
}
swap(arr,left,right);
}
if (arr[left] < cur){
swap(arr,first,left);
return left;
}else{
swap(arr,first,left - 1);
return left - 1;
}
}
在以基准元素划分的时候，可以有多种方法，除了上面的Hoare法之外，还有挖坑法
==挖坑法：==思想：取第一个元素为基准，相当于第一个位置就是一个坑，然后右指针从右向左找到小于基准值的元素放到坑处，然后当前位置就变为了坑，然后
//挖坑法
private static int test1(int[] arr,int left,int right){
//定义好基准数字,并先在left处挖一个坑
int cur = arr[left];
while(left < right){
while (left < right){
if (arr[right] < cur){
arr[left] = arr[right];
break;
}
right--;
}
while (left < right){
if(arr[left] > cur){
arr[right] = arr[left];
break;
}
left++;
}
}
arr[left] = cur;
return left;
}
快排复杂度
🔑==快排时间复杂度分析：==如果对于待排序数组，每次递归后都会分为两个左右一样长的序列，那这颗树的高度就是logN，而对于这棵树的每一层来说，第一层是N个节点，以下每一层都比上一层少一个节点，每一层按照Hoare法或者挖坑法来计算。平均每一层的时间复杂度是O(N/2)，总共logN层，所以时间复杂度是O(N * logN)。所以可以看出，不管怎么分，分出多少个子序列，子序列的长度总和都是原数组的长度。所以每一层的时间复杂度都是O(N)，总体的时间复杂度关键在于树的高度。最好情况下是每次平均分成两个等长子序列。那树的高度就是O(logN)。
那最坏情况下，数组已经有序，比如1,2,3,4,5,6。那每一次分出来的子序列都是原序列少一个元素，那树的高度是N，第一层共N个元素，第二层N-1个元素，第三层N-2个元素，依次递减。所以总体时间复杂度是O(N * N)。
❤️总结最好情况下：O(N * logN)，最坏情况下：O(N * N)
🔑==快排空间复杂度分析：==空间复杂度需要看递归的深度，也就是树的高度，时间复杂度那里已经分析了，树的高度最低logN，最高N，所以空间复杂度最好O(logN)，最坏是O(N)
快排优化
快速排序在数据量比较大的情况下，而且数据比较有序的情况下会出现栈溢出。因为最坏情况下空间复杂度是O(N)。那针对这种问题就需要优化快排
==优化一：==对于待排序区间较小的情况可以直接改为插入排序，因为快排越往下递归，序列越趋于有序。因为每次递归，都让小于基准的在左侧，大于基准的在右侧。而插入排序是序列越有序，插入越快。最好情况下是O(N)。 代码已经在上面实现。而且也可以减少递归的深度，可以改善递归深度太大挤爆栈的问题。
优化二：对于有序的情况下，每次选最左面元素作为基准，空间复杂度还是太高，方式一不能从根本上解决问题。所以在找基准这方面还可以改进。比如每次从当前序列中随机选取一个元素作为基准，这样对于有序的情况下可以解决问题。
🔑方式一：
private static void quick(int[] arr,int left,int right){
if(left >= right){
return;
}
//小区间采用插入排序
if (right - left <= 500){
insert1Sort(arr,left,right);
return;
}
//从序列中随机选取一个值作为基准。
Random random = new Random();
int randomIndex = random.nextInt(right - left + 1) + left;
swap(arr,left,randomIndex);
//使基准左侧数字都小于基准，基准右侧数字都大于基准，然后返回基准的下标
int index = test1(arr,left,right);
//排序左半个数组
quick(arr,left,index - 1);
//排序右半个数组
quick(arr,index + 1,right);
}
在测试代码中，如果给的数据是100000个有序数据，不加随机数这一优化，会出现栈溢出，而加上这一优化后，就不会再出现栈溢出这种情况。
🔑方式二：除了随机选取一个数作为基准，还可以采取三数取中法，最左元素，最右元素，以及中间元素，这三个数取一个中间值作为基准。
private static void midIndex(int[] arr,int left,int right){
int mid = left+((right-left)>>>1);
if (arr[left] < arr[right]){
if (arr[mid] < arr[left]){
}else if(arr[mid] > arr[right]){
swap(arr,left,right);
}else {
swap(arr,left,mid);
}
}else {
if(arr[mid] < arr[right]){
swap(arr,left,right);
}else if(arr[mid] > arr[left]){
}else{
swap(arr,left,mid);
}
}
}
这段代码同样可以解决有序序列栈溢出的情况。100000个有序数据如果没有这段优化就会栈溢出。
✅总结：优化的两个方面：一是小区间改为直接插入排序，二是对于选取基准的优化
优化三：当根据基准进行划分之后，还可以将左右序列中与基准相同的值移动到基准的周围，然后再进行递归的时候序列中就不用有基准值了，如果重复元素比较多，这样可以有效减少递归的次数。
我们可以在用基准划分左右序列的时候顺带着将与基准相等的值交换至序列的左右两侧。然后再调用另一个函数将左右两侧的与基准相同的值交换到基准值周围。
🔑分割出左右序列，并且将与基准相同的值放置最左面和最右面
//挖坑法，并且将与基准值相等的值放置最左面和最右面
private static int test1(int[] arr,int left,int right){
//定义好基准数字,并先在left处挖一个坑
int cur = arr[left];
int low = left;
int high = right;
while(left < right){
while (left < right && arr[right]>=cur){
//将与基准值相等的元素放置最右面
if(arr[right] == cur){
swap(arr,right,high);
high--;
}
right--;
}
arr[left] = arr[right];
while (left < right && arr[left]<=cur){
//将与基准值相等的元素放置最左面
if(arr[left] == cur){
swap(arr,left,low);
low++;
}
left++;
}
arr[right] = arr[left];
}
arr[left] = cur;
return left;
}
🔑将与基准值相同的值交换至基准周围，最后返回下一次递归的左序列的结束位置和有序列的起始位置
private static int[] gather(int[] arr,int left,int right,int index){
//基准值
int tmp = arr[index];
int low = left;
int high = right;
//左边序列最右的元素
int mid1 = index - 1;
//右边序列最左的元素
int mid2 = index + 1;
//将左边序列与基准值相等元素交换到基准左侧
while (left < mid1 && arr[left] == tmp && arr[mid1] != tmp){
swap(arr,left,mid1);
left++;
mid1--;
}
//将右边序列与基准值相等元素交换到基准右侧
while (mid2 < right && arr[right] == tmp && arr[mid2] != tmp){
swap(arr,right,mid2);
right--;
mid2++;
}
int[] ret = new int[2];
int i = index;
int j = index;
while(arr[i]==tmp){
i--;
}
while (arr[j]==tmp){
j++;
}
ret[0] = i;
ret[1] = j;
return ret;
}
✅聚集基准值这种优化当重复元素比较多的时候优化效果明显，当重复元素比较少的时候优化效果不明显，而且还有可能拖慢排序速度。
除了上述几种优化方式之外，还有尾递归优化，还有多线程优化。
快排非递归
//非递归快速排序
public static void quickSortNor(int[] arr){
Stack<Integer> stack = new Stack<>();
//左右区间入栈
stack.push(0);
stack.push(arr.length-1);
while (!stack.isEmpty()){
int right = stack.pop();
int left = stack.pop();
int index = test(arr,left,right);
if(index-left>=2){
stack.push(left);
stack.push(index-1);
}
if (right-index>=2){
stack.push(index+1);
stack.push(right);
}
}
// Queue<Integer> queue = new LinkedList<>();
// queue.offer(0);
// queue.offer(arr.length-1);
// while (!queue.isEmpty()){
// int left = queue.poll();
// int right = queue.poll();
// int index = test(arr,left,right);
// if(index-left >= 2){
// queue.offer(left);
// queue.offer(index-1);
// }
// if (right-index >= 2){
// queue.offer(index+1);
// queue.offer(right);
// }
// }
}
快速排序的非递归版本需要借助辅助空间，借助栈或者队列，首先将待排序序列的区间入栈，然后循环里是出一组区间，然后对这一区间划分左右序列，然后再将左右序列入栈（如果序列至少有两个元素的话）。等栈空的时候，数组排序完毕。
当划分出的左右序列至少有两个元素的时候才入栈，这是栈最后能为空（循环能终止的条件）。
归并排序
⭕️归并排序和快排一样也用的是分治的思想，只不过实现的方式不一样，快排是用一个基准值分隔出左右序列，然后再分别对左右序列排序。归并是先将序列分成左右两等份，然后分别将左右序列排序，最后再将左右序列合并排序。
private static void merge(int[] arr, int left, int right) {
int mid = left + ((right - left)>>>2);
int bound = right - left + 1;
int[] tmp = new int[bound];
int index = 0;
int i = left;
int j = mid + 1;
while(i <= mid && j <= right){
if (arr[i] < arr[j]){
tmp[index++] = arr[i++];
}else{
tmp[index++] = arr[j++];
}
}
while (i <= mid){
tmp[index++] = arr[i++];
}
while (j <= right){
tmp[index++] = arr[j++];
}
for (int k = 0; k < tmp.length; k++) {
arr[left++] = tmp[k];
}
}
private static void mergeSortBound(int[] arr,int left,int right){
if(left >= right){
return;
}
int mid = left + ((right - left)>>>2);
//递归将左右序列排序
mergeSortBound(arr,left,mid);
mergeSortBound(arr,mid+1,right);
//将左右序列整合排序
merge(arr,left,right);
}
public static void mergeSort(int[] arr){
mergeSortBound(arr,0,arr.length - 1);
}
🔑时间复杂度：O(N * logN)，由于每一次都是把序列对半分，所以这颗树的高度就是logN，而每一层元素都是N个，每一层整合的时间复杂度是O(N)，所以总共的时间复杂度是O(N * logN)
🔑空间复杂度：递归的树的高度是logN，所以从函数栈桢考虑复杂度是O(logN)，但是在merge函数中还会开辟数组空间，当第一次调用mergeSortBound()函数执行到merge()函数时会开辟N个数组空间，所以时间复杂度是O(N)，总体时间复杂度是O(N+logN)，化简得O(N)
归并非递归
归并排序的非递归
//归并非递归
public static void mergeSortNor(int[] arr){
//每2*gap个元素合并到一起
int gap = 1;
while (gap < arr.length){
//每gap一组排序
for (int left = 0; left < arr.length; left+=gap*2) {
int mid = left+gap-1;
//越界调整
if (mid>=arr.length){
mid = arr.length-1;
}
int right = left+gap*2-1;
//越界调整
if (right>=arr.length){//right下标越界，修正为数组最后一个下标
right = arr.length - 1;
}
merge(arr,left,mid,right);
}
gap*=2;
}
}
第一次是每两个元素合并到一起，然后是每四个元素合并到一起，然后是八个元素合并到一起，直到把数组元素都合并到一起。
总结
非比较排序
以上七种排序都是基于比较的排序，还有的排序是非基于比较的排序
计数排序
⭕️计数排序原理：统计数组中每个数字出现的个数，然后再根据数字个数填充到数组中，就会得到一个有序序列。
⭕️比如现在序列中数字的范围是0~9，那就可以新创建一个大小为10的数组，数组的0下标存待排序序列中数字0的个数，数组的1下标存数字1的个数，依次类推，数组的9下标存数字9的个数。然后遍历这个统计数组，有几个0就填充到原数组中几个0，有几个1就填充几个1，依次类推。
🍎代码实现：
//计数排序
public static void countSort(int[] arr){
if (arr.length == 0){
return;
}
int min = arr[0];
int max = arr[0];
for (int i = 0; i < arr.length; i++) {
if (arr[i] < min){
min = arr[i];
}
if (arr[i] > max){
max = arr[i];
}
}
//确定范围
int bound = max - min + 1;
int[] countArr = new int[bound];
//统计数字出现次数
for (int i = 0; i < arr.length; i++) {
countArr[arr[i]-min]++;
}
//将数据写回原数组
int index = 0;
for (int i = 0; i < countArr.length; i++) {
while (countArr[i] > 0){
arr[index++] = i + min;
countArr[i]--;
}
}
}
🎃时间复杂度分析：找最大值和最小值复杂度是O(N)，统计数字出现次数复杂度是O(N)，最后将数据写回原数组复杂度是O(K+N)，因为遍历范围是O(K)，for循环中的内部while循环是O(N)，加起来是O(K+N)，注意这里并不是相乘的关系，是相加的关系。所以总的时间复杂度是O(K+N)。（K代表范围）
🎃空间复杂度分析：额外空间是统计数组，所以空间复杂度是O(K)。
所以计数排序的时间复杂度和空间复杂度是和数据的范围相关的，范围越小效率越高。
基数排序
桶排序
排序OJ题
颜色分类
OJ链接
计数排序法
class Solution {
public void sortColors(int[] nums) {
int[] count = new int[3];
//统计0,1,2出现的次数
for(int i=0;i<nums.length;i++){
int num = nums[i];
count[num]++;
}
int index = 0;
for(int i=0;i<count.length;i++){
while(count[i]>0){
nums[index++] = i;
count[i]--;
}
}
}
}
时间复杂度是O(N)，不过遍历了两遍数组。
单指针法
遍历一遍将0全部交换到最前面，遍历第二遍将2全部交换到最后面
//单指针法
class Solution {
private void swap(int[] arr,int i,int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public void sortColors(int[] nums) {
int index = 0;
for(int i=0;i<nums.length;i++){
if(nums[i]==0){
swap(nums,i,index);
index++;
}
}
for(int i=index;i<nums.length;i++){
if(nums[i]==1){
swap(nums,i,index);
index++;
}
}
}
}
时间复杂度：O(N)，遍历了两遍数组
双指针法
一个指针指向2将存放的位置，一个指针指向0将存放的位置，一次遍历排好序
//双指针法
//一次遍历将0交换至最前，将2交换至最后，1自然就在中间了
class Solution {
private void swap(int[] nums,int index1,int index2){
int tmp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = tmp;
}
public void sortColors(int[] nums) {
int p0 = 0;
int p2 = nums.length - 1;
for(int i = 0; i < nums.length; i++){
//当前位置如果是2就交换到后面
while(i < p2 && nums[i] == 2){
swap(nums,i,p2);
p2--;
}
if(nums[i] == 0){
swap(nums,i,p0);
p0++;
}
}
}
}
车队
OJ链接
class Car{
int distance;
double time;
public Car(int distance,double time){
this.distance = distance;
this.time = time;
}
}
class CmpCar implements Comparator<Car>{
public int compare(Car c1,Car c2){
return c1.distance - c2.distance;
}
}
class Solution {
public int carFleet(int target, int[] position, int[] speed) {
Car[] cars = new Car[position.length];
for(int i = 0;i < cars.length;i++){
int distance = target - position[i];
double time = distance*1.0/speed[i];
cars[i] = new Car(distance,time);
}
Arrays.sort(cars,new CmpCar());
int count = 0; //车队数量
for(int i = 0;i < cars.length;i++){
//当前车辆到达目的地所用时间
double time = cars[i].time;
int j = 0;
for(j = i+1;j < cars.length;j++){
double nextTime = cars[j].time;
if(nextTime > time){
break;
}
}
i = j - 1;
count++;
}
return count;
}
}
⭕️思路：把数组排个序，按照离终点距离由小到大排序，编号1,2,3,4等等，如果第一辆车到达终点时间比第二辆大或者相等，那这两辆车一定可以相遇，那最终两辆车到达时间就是第一辆车所需时间，然后再判断第三辆车时间是否小于这个时间，如果小于，这三辆车可以相遇（组成车队），依次类推，如果第三辆车不能相遇，那后续的第四辆，第五辆更不可能和前两辆车相遇。如果这样的话，前两辆车为一个车队，从第三辆开始，往后找到能与第三辆车组成车队的车，依次遍历完所有车队。
⭕️创建Car这个类，使用cars数组将postion数组和speed数组整合到一起是为了，当排序postion时，postion数组和speed数组中元素的位置关系仍然可以一一对应。或者我们可以自己实现一个排序，比如堆排序，当排序postion数组交换元素位置时，让speed数组也随之交换，这样就能保证postion数组排序后还能和speed数组保持元素位置关系对应。
class Solution {
private int[] speed;
private void swap(int[] arr,int index1,int index2){
//保持postion数组和speed数组元素位置关系一一对应
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
int tmp1 = speed[index1];
speed[index1] = speed[index2];
speed[index2] = tmp1;
}
private void shiftDown(int[] arr,int root,int end){
int parent = root;
int child = root*2+1;
while(child < end){
if(child+1<end && arr[child+1]<arr[child]){
child = child+1;
}
if(arr[child]<arr[parent]){
swap(arr,child,parent);
}else{
break;
}
parent = child;
child = parent*2+1;
}
}
//堆排序
private void heapSort(int[] arr){
int parent = (arr.length-1-1)/2;
//建成小根堆
while(parent >= 0){
shiftDown(arr,parent,arr.length);
parent--;
}
//降序排序
int end = arr.length - 1;
while(end > 0){
swap(arr,0,end);
shiftDown(arr,0,end);
end--;
}
}
public int carFleet(int target, int[] position, int[] speed) {
this.speed = speed;
heapSort(position);
int count = 0;
for(int i = 0;i < position.length;i++){
double curCarTime = (target - position[i])*1.0/speed[i];
int j = 0;
for(j = i+1;j<position.length;j++){
double nextCarTime = (target - position[j])*1.0/speed[j];
if(nextCarTime > curCarTime){
break;
}
}
i = j - 1;
count++;
}
return count;
}
}
排序链表
OJ链接
//归并排序
class Solution {
private void merge(ListNode begin,ListNode mid,ListNode end){
int count = 0;//count代表链表当前区间内元素个数
ListNode cur = begin;
while(cur!=end.next){
count++;
cur = cur.next;
}
int[] arr = new int[count];
int index = 0;
ListNode left = begin;
ListNode right = mid.next;
//左右区间都有节点
while(left!=mid.next && right!=null && right!=end.next){
if(left.val < right.val){
arr[index++] = left.val;
left = left.next;
}else{
arr[index++] = right.val;
right = right.next;
}
}
while(left!=mid.next){
arr[index++] = left.val;
left = left.next;
}
while(right!=null && right!=end.next){
arr[index++] = right.val;
right = right.next;
}
ListNode curNode = begin;
for(int i = 0;i < arr.length;i++){
curNode.val = arr[i];
curNode = curNode.next;
}
}
public ListNode sortList(ListNode head) {
if(head == null){
return null;
}
//count代表链表长度
int count = 0;
ListNode curNode = head;
ListNode parent = null; //parent最终指向链表最后一个元素
while(curNode!=null){
count++;
parent = curNode;
curNode = curNode.next;
}
int gap = 1;
while(gap < count){
ListNode cur = head;
while(cur!=null){
int len = gap;
ListNode mid = cur;
while( mid != null && len - 1 > 0){
mid = mid.next;
len--;
}
//越界则指向最后一个元素
if(mid==null){
mid = parent;
}
ListNode end = mid;
len = gap;
while(end!=null && len > 0){
end = end.next;
len--;
}
//越界则指向链表最后一个元素
if(end==null){
end = parent;
}
merge(cur,mid,end);
cur = end.next;
}
gap*=2;
}
return head;
}
}
⭕️排序链表思路：排序链表使用的排序是归并排序的思想，时间复杂度是O(logN)，空间复杂度是O(N)，主要是在merge函数中创建了数组，而当前是链表可以改变指针指向，可以省去数组，直接更改指向达到O(1)的空间复杂度
⭕️代码实现：