排序算法超详细代码和知识点整理(java版)

排序

1、冒泡排序

​ 两层循环，相邻两个进行比较，大的推到后面去，一共比较“数组长度”轮，每一轮都是从第一个元素开始比较，每一轮比较都会将一个元素固定到数组最后的一个位置。【其实就是不停的把元素往后堆，数组剩余长度越来越少，直到堆到最后一个，数组都堆好排好序了】

if (arr == null || arr.length < 2) return;
for (int e = arr.length - 1; e > 0; e--) {for (int i = 0; i < e; i++) {if (arr[i] > arr[i + 1]) {swap(arr, i, i + 1); } } }

2、选择排序

​ 也是比较**“数组长度-1”轮，但是每一轮中是将一个最值元素放在开头**，然后从这个更新过元素的位置往后继续开始此轮的选择最值过程【其实就是不停的从选择最小元素，然后往前堆，和冒泡正好相反，然后前面剩余空间越来越少，直到前面都堆好了排好序了】

if (arr == null || arr.length < 2) return;
for(int i=0; i<arr.length - 1; i++){int minIndex = i;for(int j=i+1; j<arr.length; j++){minIndex = arr[j] < arr[minIndex] ? j : minIndex;} swap(arr,i,minIndex);
}

3、插入排序

​ 重点看当前索引指向的元素大小，去对比比当前索引小，也就是前面排好序的那一部分元素。找到合适的位置，然后插进去。这对比的次数明显变少，只用和【索引-1】前面的数进行比较。

if (arr == null || arr.length < 2) return;
for(int i = 1; i<arr.length; i++)for(int j = i-1; arr[j+1]<arr[j] && j >= 0; j--)swap(arr,j,j+1);

4、快速排序

​ 本质是找个基准值，一般可以选取这段数组中的最后一个元素。然后将小于这个基准值的放在其左侧，大于的放在其右侧.

​ 在遍历数组时，一般采用三指针法来实现。具体来说，我们使用一个左指针指向数组的左边界，用一个右指针指向数组的右边界。另外一个指针指向元素，用来遍历。

• 如果当前查找的索引值对应数据 arr [i] 小于基准值，那么这个值和左边界【左指针】的下一个进行交换，同时左指针右移；

• 如果大于基准值，就将其和右边界的前一个元素交换，同时左边界指针不动。索引 i 也不动，但是右指针左移

• 如果等于基准值，索引 i ++

public static void quickSort(int[] arr){if(arr == null || arr.length < 2)return;quickSort(arr,0,arr.length-1);
}public static void quickSort(int[] arr, int l, int r){if(l < r){int[] p = partition(arr,l,r);  //作用就是将最后一个元素当作基准值，然后将大于基准值得放右边，小于的放左边//同时，返回一个基准信息,p[0]就是基准值中最左的一个【考虑到可能标志值会重复】，p[1]是最右侧quickSort(arr, l, p[0] - 1);quickSort(arr, p[1] + 1, r);}
}public static void partiton(int[] arr, int l, int r){ //l是左边界，int pivot = arr[r];int left = l -1;int right = r;while(l < right){            //arr[l]，就用来记录逐步遍历数组中的元素if(arr[l] < pivot)swap(arr, ++left, l++); // 将小于等于pivot的元素交换到左边界的右侧else if(arr[l] > pivot){swap(arr, --right, l); // 将大小于等于pivot的元素交换到右边界的左侧}elsel++;}swap(arr, more, r); //最后将基准值转移到右指针位置return new int[] { less + 1, more };
}

5、归并排序

​ 将数组按照中间的位置，划分成左右两部分，然后对这两部分进行扫描归并。准备两个指针，分别指向左部分的开头，以及有部分的开头。然后比较大小，按照比较结果，将结果放进一个临时开辟的数组中，最后将这个临时数组的元素再塞回去。

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 l, int r){if(l < r){int mid = l + ((r-l)>>1;mergeSort(arr, l, mid+1);mergeSort(arr, mid+1, r);     merge(arr,l,mid,r);}
}public static void merge(int[] arr, int l, int mid, int r) {int[] help = new int[r - l + 1];int i = 0;int p1 = l;int p2 = mid + 1;while(p1 <= mid && p2 <= r){help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];}while (p1 <= m) {help[i++] = arr[p1++];}while (p2 <= r) {help[i++] = arr[p2++];}for (i = 0; i < help.length; i++) {arr[l + i] = help[i];}
}

6、堆排序

主要涉及两步骤：

1、构建堆【heapInsert】，2、输出堆顶元素，然后调整堆结构，以便于下一轮继续输出堆顶元素【heapify】

构建堆的过程就是不停的往上，也就是和自己的父节点、祖父节点…一直比较下去，如果想要大根堆，那就是只要大于父节点，那就和父节点交换，我们对数组的每一个元素都去单独构建一边。

调整堆，就是不停的往下。将堆顶元素和数组最后元素交换，由于当前数组经过构建堆过程后，已经是堆结构了。所以我们的堆顶元素肯定就是一个最值，交换过后，再重新调整堆即可。就是找到堆顶的孩子节点中最大的值，进行比较交换，一直比较到树的最后一层

public static void heapSort(int[] arr) {   //这个是主函数，参数中的arr数组中存放的就是待排元素if (arr == null || arr.length < 2) {return;}for (int i = 0; i < arr.length; i++) { //这个函数是用于创建大根堆，为了之后输出堆顶元素就是最大值heapInsert(arr, i);}int size = arr.length;    			  swap(arr, 0, --size);	//这一步是为了将堆顶元素和最后一个元素互换位置，注意最后要自减 也就是说最后应该数组中元素是从小到大排序的（如果一开始是一个大根堆）while (size > 0) {heapify(arr, 0, size);swap(arr, 0, --size); //同上面道理}
}
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 ;           //这一步别忘记了，一直是往下走的，index这个表示父节点位置的标记变量也要向下走}
}
public static void heapify(int[] arr, int index, int size) {//这次函数中参数中要借助 堆的大小size（对应上面主函数中的每次输出一次堆顶元素后，大小减1）int left = index * 2 + 1;while (left < size) {int largest = left + 1 < size && 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) {       //就是一个交换函数，C++中直接用swap函数即可int tmp = arr[i];  arr[i] = arr[j];  arr[j] = tmp; }

7、优先级队列

默认是小根堆

//小根堆。默认
PriorityQueue<Integer> heap = new PriorityQueue<>();

• 在左神算法讲解时举了一个例子，就是;

  堆排序扩展题目:
  已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。
  

  这时候就需要借助 堆结构 一开始先将前k个数存放入此优先级队列，也就是堆结构，然后将堆顶元素返回，也就是用pop返回

  这k个元素构成一个堆结构，找到这个堆中的小根堆的堆顶元素，就是当前最小的

  因为每个元素移动的距离不超过k，所以可以理解为这前k个数中最小的一个属肯也是整体数据中最小的一个数字，把第k+1个数放进去，再次形成小根堆，那返回的堆顶元素就是第二小的元素

  然后再重新从数组中取下一个元素，添加到堆中，自动就排好序形成相应的大根堆或者是小根堆

• 下面我用左神算法中的java 代码来展示，其中关键的地方都加了注释了：

public void sortedArrDistanceLessK(int[] arr, int k) {PriorityQueue<Integer> heap = new PriorityQueue<>();  //java中的优先级队列的定义方式int index = 0;for (; index < Math.min(arr.length, k); index++) {//万一k超出范围了，就选取数组长度当作边界值，min()的作用就是这个heap.add(arr[index]);}int i = 0;for (; index < arr.length; i++, index++) {heap.add(arr[index]);  //上面那个for循环实际上没有取到第k个元素，所以先取arr[i] = heap.poll();  //然后再弹出堆顶元素}while (!heap.isEmpty()) {//数组最后一个元素也都加进堆结构后，剩下的就是将堆中的所有元素放依次弹出了arr[i++] = heap.poll();}
}

8、复杂度

• 冒泡：时间复杂度o(n^2) 空间复杂度O(1)（原地排序，不需要额外空间）
• 选择：时间复杂度o(n^2) 空间复杂度O(1)（原地排序，不需要额外空间）
• 插入：时间复杂度o(n^2) 空间复杂度O(1)（原地排序，不需要额外空间）
• 快速：时间复杂度o(nlogN) 空间复杂度平均情况下是O(log n)，最坏情况下是O(n)。
• 归并：时间复杂度o(nlogN) 空间复杂度O(n)（需要额外的空间来合并子数组）
• 堆 ：时间复杂度o(nlogN) 空间复杂度O(1)（原地排序）