排序算法超详细代码和知识点整理(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的元素交换到右边界的左侧
        }
        else
            l++;
    }
    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();
    }
}