排序.md

# 排序

所谓排序算法，即通过特定的算法因式将一组或多组数据按照既定模式进行重新排序。这种新序列遵循着一定的规则，体现出一定的规律，因此，经处理后的数据便于筛选和计算，大大提高了计算效率。

对于排序：

- 我们首先要求其具有一定的稳定性
- 即当两个相同的元素同时出现于某个序列之中
- 则经过一定的排序算法之后
- 两者在排序前后的相对位置不发生变化。

> 所以，就让我们先来看看，面试中，有哪些超高频的排序算法

----





### 一、冒泡排序  ★★★★★

- 冒泡排序可以说是最基础的了，无非就是两个 for 循环嵌套，然后两两比较交换罢了。这就不多说了。

##### 步骤：

1、比较相邻的元素。如果第一个比第二个大（小），就交换他们两个。

2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大（小）的数。

3、针对所有的元素重复以上的步骤，除了最后已经选出的元素（有序）。

4、持续每次对越来越少的元素（无序元素）重复上面的步骤，直到没有任何

![冒泡排序](https://user-gold-cdn.xitu.io/2019/10/11/16db82e95ded40d1?w=988&h=483&f=png&s=378901)

##### 视频：
- [数据结构排序算法之冒泡排序演示](https://www.bilibili.com/video/av18176281?from=search&seid=7859791752267456551)

##### 示例代码：

```java
public void bubbleSort(int[] arr) {
    int temp = 0;
    boolean swap;
    for (int i = arr.length - 1; i > 0; i--) { // 每次需要排序的长度
        // 增加一个swap的标志，当前一轮没有进行交换时，说明数组已经有序
        swap = false;
        for (int j = 0; j < i; j++) { // 从第一个元素到第i个元素
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swap = true;
            }
        }
        if (!swap){
            break;
        }
    }
}
```

<br>
<br>

----





### 二、归并排序   ★★★★★

- 对于归并排序而言，思想可以概括为：分而治之。也就是将一个数组，首先划分为一堆单个的数，然后再一个接一个的，进行两两有序合并，最后就得到了一个有序数组。

##### 步骤：

 1. 将待排序的数列分成若干个长度为1的子数列 

 2. 然后将这些数列两两合并；得到若干个长度为2的有序数列

 3. 再将这些数列两两合并；得到若干个长度为4的有序数列

 4. 再将它们两两合并；直接合并成一个数列为止

 5. 这样就得到了我们想要的排序结果

![归并排序](https://user-gold-cdn.xitu.io/2019/10/11/16db82e95ec8ec37?w=1768&h=1354&f=png&s=249885)

##### 视频：

- [归并排序](https://www.bilibili.com/video/av9982752?from=search&seid=3867655594439600775)

##### 示例代码：

```java
// 入口
public void mergeSort(int[] arr) {
    int[] temp = new int[arr.length];
    internalMergeSort(arr, temp, 0, arr.length - 1);
}

private void internalMergeSort(int[] arr, int[] temp, int left, int right) {
    // 当left == right时，不需要再划分
    if (left < right) {
        int mid = (left + right) / 2;
        // 左右往下拆分
        internalMergeSort(arr, temp, left, mid);
        internalMergeSort(arr, temp, mid + 1, right);
        // 拆分结束后返回结果进行合并
        mergeSortedArray(arr, temp, left, mid, right);
    }
}

// 合并两个有序子序列
public void mergeSortedArray(int[] arr, int[] temp, int left, int mid, int right) {
    int i = left;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= right) {
        temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
    }
    // 合并完，将非空的那列拼入
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    // 把temp数据复制回原数组
    for (i = 0; i < k; i++) {
        arr[left + i] = temp[i];
    }
}
```

<br>
<br>

----







### 三、快速排序 ⭐️⭐️⭐️⭐️⭐️

快速排序的思想，可以简单的概括为：两边包抄、一次一个。每选一个基准点，一次排序后确定它的最终位置，一步到位。

##### 步骤：

1、先从数列中取出一个数作为基准数

2、分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边

3、再对左右区间重复第二步，直到各区间只有一个数

概括来说为 挖坑填数+分治法

![快速排序](https://user-gold-cdn.xitu.io/2019/10/11/16db82e95ebb11b8?w=913&h=707&f=jpeg&s=108152)

> 注： 快排算法不唯一，到目前为止我已经看到三种排法，这里我用最老的，就是很多教材上的排法解析

##### 视频：

- [快速排序算法](https://www.bilibili.com/video/av62621532?from=search&seid=12427700653335036249)

##### 示例代码：

```java
public void quickSort(int[] arr){
    quickSort(arr, 0, arr.length-1);
}

private void quickSort(int[] arr, int low, int high){
    if (low >= high)
        return;
    int pivot = partition(arr, low, high);        //将数组分为两部分
    quickSort(arr, low, pivot - 1);                   //递归排序左子数组
    quickSort(arr, pivot + 1, high);                  //递归排序右子数组
}

private int partition(int[] arr, int low, int high){
    int pivot = arr[low];     //基准
    while (low < high){
      	// 注意 low 设为 pivot 后，必须先走 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;
}
```

<br>
<br>

----

### 计数排序  ⭐️⭐️⭐️⭐️⭐️	

- 求大小 - 初始化 - 刷新 - 附值

计数排序顾名思义，其思想就在于记录各个数的出现次数，最后按顺序取出即可。

##### 步骤：

1. 建一个长度为K+1的的数组C，里面的每一个元素初始都置为0(Java里面默认就是0)。

2. 遍历待排序的数组，计算其中的每一个元素出现的次数，比如一个key为i的元素出现了3次，那么C[i]=3。

3. 累加C数组，获得元素的排位，从0开始遍历C, C[i+1]=C[i]+C[i-1]

4. 建一个临时数组T，长度与待排序数组一样。从数组末尾遍历待排序数组，把元素都安排到T里面，直接从C里面就可以得到元素的具体位置， 不过记得每处理过一个元素之后都要把C里面对应位置的计数减1。

![计数排序](https://user-gold-cdn.xitu.io/2019/10/11/16db82e965390130?w=1243&h=702&f=png&s=60809)
##### 视频：

- [计数排序算法可视化解读](https://www.bilibili.com/video/av33398531?from=search&seid=13929265504985748035)

##### 示例代码：
- 我在网上看了巨多代码，但基本都是用来处理 0 以上数的计数排序。下面介绍的这个算法，可以适应小于 0 的数的计数排序，我加了很多注释，也很好理解：

```java
public void countSort(int[] arr) {
	// 找到最大值和最小值
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < arr.length; i++){
        max = Math.max(max, arr[i]);
        min = Math.min(min, arr[i]);
    }

    int[] b = new int[arr.length]; // 存储数组
    int[] count = new int[max - min + 1]; // 计数数组

    for (int i = 0; i < arr.length; i++) {
        int num = arr[i];
        count[num - min]++; // 每出现一个值，计数数组对应元素的值+1
        // 此时count[i]表示数值等于i的元素的个数
    }

    for (int i = 1; i < count.length; i++) {
			count[i] += count[i-1];
		}

    for (int i = 0; i < arr.length; i++) {
        int num = arr[i]; // 原数组第i位的值
        int index = count[num - min] - 1; //加总数组中对应元素的下标
        b[index] = num; // 将该值存入存储数组对应下标中
        count[num - min]--; // 加总数组中，该值的总和减少1。
    }

    // 将存储数组的值替换给原数组
    for(int i=0; i < arr.length;i++){
        arr[i] = b[i];
    }
}
```

<br>
<br>

----

### 桶排序 ★★★★★★

桶排序的思想是，首先按特定规则，划分出若干个’桶‘，每个‘桶’有个范围，将大小在对应‘桶’范围内的数，对号入座。再依次将每个‘桶’内的数有序排列，最后按顺序拼接各个‘桶’即可。

##### 步骤：

1. 根据待排序集合中最大元素和最小元素的差值范围和映射规则，确定申请的桶个数；
2. 遍历待排序集合，将每一个元素移动到对应的桶中；
3. 对每一个桶中元素进行排序，并移动到已排序集合中。
> 步骤 3 中提到的已排序集合，和步骤 1、2 中的待排序集合是同一个集合。与计数排序不同，桶排序的步骤 2 完成之后，所有元素都处于桶中，并且对桶中元素排序后，移动元素过程中不再依赖原始集合，所以可以将桶中元素移动回原始集合即可。

![桶排序](https://user-gold-cdn.xitu.io/2019/10/11/16db82e96978d367?w=350&h=250&f=jpeg&s=17803)

##### 视频：

- [桶排序](https://www.bilibili.com/video/av55573441?from=search&seid=2289099632525203298)

##### 示例代码：

上面讲的计数排序其实一定程度上，也可以看作一种特殊的桶排序，同样的，网上桶排序代码大一堆，啥语言都有。但却没有一个解决小于 0 数排序问题的，要么就不处理要么就抛出异常，下面这个算法，有效的解决了，小于 0 数排序的难题

```java
public static void bucketSort(int[] arr){
	// 首先还是找出最大、最小值
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < arr.length; i++){
        max = Math.max(max, arr[i]);
        min = Math.min(min, arr[i]);
    }
    
    // 桶数
    // 在桶排序中，对桶的划分个数是随意的
    // 这个方法划分的桶数量随带划分数列的密集程度改变而改变
    int bucketNum = (max - min) / arr.length + 1;
    ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
    // 初始化各个桶
    for(int i = 0; i < bucketNum; i++){
        bucketArr.add(new ArrayList<Integer>());
    }
    
    // 将每个元素放入相应的桶
    for(int i = 0; i < arr.length; i++){
        int num = (arr[i] - min) / (arr.length);
        bucketArr.get(num).add(arr[i]);
    }
    
    // 对每个桶进行排序
    for(int i = 0; i < bucketArr.size(); i++){
        Collections.sort(bucketArr.get(i));
        for (int j = 0; j < bucketArr.get(i).size(); j++) {
            arr[j] = bucketArr.get(i).get(j);
        }
    }
}
```

<br>
<br>

----