<h1>排序算法</h1>
<h2>一. 快速排序</h2>
<h3>1. 由来</h3>
<p><a href="https://baike.baidu.com/item/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/369842">快速排序</a>由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。</p>
<h3>2. 排序流程</h3>
<p>快速排序算法通过多次比较和交换来实现排序，其排序流程如下：</p>
<ol>
<li>首先设定一个分界值，通过该分界值将数组分成左右两部分。</li>
<li>将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。</li>
<li>然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。</li>
<li>重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。</li>
</ol>
<h3>3. 排序步骤</h3>
<p>假设数组arr为：{5，3，7，6，4，1，0，2，9，10，8}</p>
<ol>
<li>
<p>取 i = 0，j = 10，5为关键字x，把5记录下来后可以当作原本5的位置现在留下了一个坑，用删除线标记。</p>
<p>{<s>5</s>，3，7，6，4，1，0，2，9，10，8}</p>
</li>
<li>
<p>从右往左找到一个比x小的值，此时 j = 7，arr[j] = 2，把找到的值填入上一步的坑。</p>
<p>{2，3，7，6，4，1，0，<s>2</s>，9，10，8}</p>
</li>
<li>
<p>再从左往右找到一个比x大的数，此时 i = 2，arr[i] = 7，挖出来填入上一步的坑。</p>
<p>{2，3，<s>7</s>，6，4，1，0，7，9，10，8}</p>
</li>
<li>
<p>继续从后向前找到一个比x小的值，此时 j = 6，arr[j] = 0，填坑。</p>
<p>{2，3，0，6，4，1，<s>0</s>，7，9，10，8}</p>
</li>
<li>
<p>继续从前向后找到一个比x大的值，此时 i = 3，arr[i] = 6，填坑。</p>
<p>{2，3，0，<s>6</s>，4，1，6，7，9，10，8}</p>
</li>
<li>
<p>继续从后向前找到一个比x小的值，此时 j = 5，arr[j] = 1，填坑。</p>
<p>{2，3，0，1，4，<s>1</s>，6，7，9，10，8}</p>
</li>
<li>
<p>继续从前向后找比x大的值，i，j之间找不时，把x填入最后的坑中。</p>
<p>{2，3，0，1，4，5，6，7，9，10，8}</p>
</li>
<li>
<p>以关键字为分界线，对{2，3，0，1，4}和{6，7，9，10，8}递归调用以上步骤。</p>
</li>
</ol>
<h3>4. 代码</h3>
<pre><code class="language-java">//时间复杂度O (nlogn)
void quick_sort(int[] s, int l, int r){
    //l为左起始索引，r为右结束索引，
    //算法的定义为排序s数组的l-r的部分
    if (l &lt; r){
        //初始化
        int i = l, j = r, x = s[l];
        //最终当i==j时跳出循环
        while (i &lt; j){
            // 从右向左找第一个小于x的数
            while(i &lt; j &amp;&amp; s[j] &gt;= x) 
                j--;  
            if(i &lt; j) 
                //把j位置上的数填入i上，然后让i++
                s[i++] = s[j];
            // 从左向右找第一个大于x的数
            while(i &lt; j &amp;&amp; s[i] &lt;= x) 
                i++;  
            if(i &lt; j) 
                //把i位置上的数填入j上，然后让j--
                s[j--] = s[i];
        }
        //最后把关键字填入最后的坑
        s[i] = x;
        // 递归调用 
        quick_sort(s, l, i - 1); 
        quick_sort(s, i + 1, r);
    }
}
</code></pre>
<h3>5. 图解</h3>
<p><img src="https://www.runoob.com/wp-content/uploads/2019/03/quickSort.gif" alt=""></p>
<p>（来源菜鸟教程）</p>
<h2>二. 冒泡排序</h2>
<h3>1. 代码</h3>
<pre><code class="language-java">//时间复杂度O(n²)
void bubbleSort(int[] arr) {
    for(int i =0 ; i&lt;arr.length-1 ; i++) {
        for(int j=0 ; j&lt;arr.length-1-i ; j++) {
            if(arr[j]&gt;arr[j+1]) {
                int temp = arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
}
</code></pre>
<h3>2. 图解</h3>
<p><img src="https://www.runoob.com/wp-content/uploads/2019/03/bubbleSort.gif" alt=""></p>
<p>（来源菜鸟教程）</p>
<h2>三. 选择排序</h2>
<h3>1. 代码</h3>
<pre><code class="language-java">//时间复杂度O(n²)
public int[] sort(int[] arr) {
    // 总共要经过 N-1 轮比较
    for (int i = 0; i &lt; arr.length - 1; i++) {
        int min = i;
        // 每轮需要比较的次数 N-i
        for (int j = i + 1; j &lt; arr.length; j++) {
            if (arr[j] &lt; arr[min]) {
                // 记录目前能找到的最小值元素的下标
                min = j;
            }
        }
        // 将找到的最小值和i位置所在的值进行交换
        if (i != min) {
            int tmp = arr[i];
            arr[i] = arr[min];
            arr[min] = tmp;
        }
    }
    return arr;
}
</code></pre>
<h3>2. 图解</h3>
<p><img src="https://www.runoob.com/wp-content/uploads/2019/03/selectionSort.gif" alt=""></p>
<p>（来源菜鸟教程）</p>


# 排序算法

## 一. 快速排序

### 1. 由来

[快速排序](https://baike.baidu.com/item/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/369842)由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

### 2. 排序流程

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

1. 首先设定一个分界值，通过该分界值将数组分成左右两部分。
2. 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
3. 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

### 3. 排序步骤

假设数组arr为：{5，3，7，6，4，1，0，2，9，10，8}

1. 取 i = 0，j = 10，5为关键字x，把5记录下来后可以当作原本5的位置现在留下了一个坑，用删除线标记。

   {~~5~~，3，7，6，4，1，0，2，9，10，8}

2. 从右往左找到一个比x小的值，此时 j = 7，arr[j] = 2，把找到的值填入上一步的坑。

   {2，3，7，6，4，1，0，~~2~~，9，10，8}

3. 再从左往右找到一个比x大的数，此时 i = 2，arr[i] = 7，挖出来填入上一步的坑。

   {2，3，~~7~~，6，4，1，0，7，9，10，8}

4. 继续从后向前找到一个比x小的值，此时 j = 6，arr[j] = 0，填坑。

   {2，3，0，6，4，1，~~0~~，7，9，10，8}

5. 继续从前向后找到一个比x大的值，此时 i = 3，arr[i] = 6，填坑。

   {2，3，0，~~6~~，4，1，6，7，9，10，8}

6. 继续从后向前找到一个比x小的值，此时 j = 5，arr[j] = 1，填坑。

   {2，3，0，1，4，~~1~~，6，7，9，10，8}

7. 继续从前向后找比x大的值，i，j之间找不时，把x填入最后的坑中。

   {2，3，0，1，4，5，6，7，9，10，8}

8. 以关键字为分界线，对{2，3，0，1，4}和{6，7，9，10，8}递归调用以上步骤。

### 4. 代码

```java
//时间复杂度O (nlogn)
void quick_sort(int[] s, int l, int r){
    //l为左起始索引，r为右结束索引，
    //算法的定义为排序s数组的l-r的部分
    if (l < r){
        //初始化
        int i = l, j = r, x = s[l];
        //最终当i==j时跳出循环
        while (i < j){
            // 从右向左找第一个小于x的数
            while(i < j && s[j] >= x) 
                j--;  
            if(i < j) 
                //把j位置上的数填入i上，然后让i++
                s[i++] = s[j];
            // 从左向右找第一个大于x的数
            while(i < j && s[i] <= x) 
                i++;  
            if(i < j) 
                //把i位置上的数填入j上，然后让j--
                s[j--] = s[i];
        }
        //最后把关键字填入最后的坑
        s[i] = x;
        // 递归调用 
        quick_sort(s, l, i - 1); 
        quick_sort(s, i + 1, r);
    }
}
```

### 5. 图解

![](https://www.runoob.com/wp-content/uploads/2019/03/quickSort.gif)

（来源菜鸟教程）

## 二. 冒泡排序

### 1. 代码

```java
//时间复杂度O(n²)
void bubbleSort(int[] arr) {
    for(int i =0 ; i<arr.length-1 ; i++) {
        for(int j=0 ; j<arr.length-1-i ; j++) {
            if(arr[j]>arr[j+1]) {
                int temp = arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
}
```

### 2. 图解

![](https://www.runoob.com/wp-content/uploads/2019/03/bubbleSort.gif)

（来源菜鸟教程）

## 三. 选择排序

### 1. 代码

```java
//时间复杂度O(n²)
public int[] sort(int[] arr) {
    // 总共要经过 N-1 轮比较
    for (int i = 0; i < arr.length - 1; i++) {
        int min = i;
        // 每轮需要比较的次数 N-i
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[min]) {
                // 记录目前能找到的最小值元素的下标
                min = j;
            }
        }
        // 将找到的最小值和i位置所在的值进行交换
        if (i != min) {
            int tmp = arr[i];
            arr[i] = arr[min];
            arr[min] = tmp;
        }
    }
    return arr;
}
```

### 2. 图解

![](https://www.runoob.com/wp-content/uploads/2019/03/selectionSort.gif)

（来源菜鸟教程）

评论区 | 共 0 条评论