排序算法—八大排序

系统管理员 2021-11-08 21:32 440阅读 0赞

## 八大排序算法 ##

### 1.冒泡排序 ###

冒泡排序是一种交换排序, 就是两两比较待排序的元素, 若次序不满足要求则交换, 知道整个数组有序

**基本思想** : 每次找到最大或最小值, 然后放到首位或最后一位

对于长度为n 的数组, 因为只需要找到n-1个数的位置, 最后一个就已经确定了. 所以我们外部循环需要从0 ~ n-2. 内部循环从 n-1到 i+1, 内部循环每次将最大值或最小值推到i的位置(即选出第i小或第i大的数). 往复n-1次, 就完成了排序

public void bubbleSort(int[] array) {
        
            int n = array.length;
            for (int i = 0; i < n - 1; ++i) {
        
                boolean flag = false;
                for (int j = n -1; j > i ; --j) {
        
                    if (array[j] < array[j-1]) {
        
                        int tmp = array[j];
                        array[j] = array[j-1];
                        array[j-1] = tmp;
                        flag = true;
                    }
                }
                if (!flag) {
        
                    break;
                }
            }
        }

**优化方案** : 添加一个标记位flag, 每次内部循环之前给它置flase, 如果发生了交换, 则给它赋值为true, 每次内部循环后进行一次检验, 如果本次内循环没有发生数据交换(即flag仍为flase), 就说明数组已经有序, 就没有必要继续进行外部的大循环了, 直接break, 排序结束

<table> 
 <thead> 
  <tr> 
   <th>参数</th> 
   <th>结果</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>排序方法</td> 
   <td>冒泡排序</td> 
  </tr> 
  <tr> 
   <td>平均时间复杂度</td> 
   <td>O(N^2)</td> 
  </tr> 
  <tr> 
   <td>空间复杂度</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>稳定性</td> 
   <td>稳定</td> 
  </tr> 
 </tbody> 
</table>

### 2.快速排序 ###

和冒泡排序一样, 快速排序也是一种交换排序, 但是快速排序是使用率最高的排序方法, 并且效率很高

**基本思想 :** 通过一趟排序将要排序的数据分割成独立的两部分 : 分割点左边都是比它小的数, 右边都是比它大的数.再按此方法对这两部分数据分别进行快速排序, 整个排序过程可以递归进行, 从此达到整个数据变成有序序列.

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dpbnRlcnNoaWk_size_16_color_FFFFFF_t_70]

过程 : 挑选数组第一个数作为数组的base(枢轴值), left和right各在数组的两边, 从right指针开始比较, 如果遇到比base值更小的数, 则将其放在left位置上. 然后再从left指针开始向右扫描, 遇到比base更大的数则放在right位置上, 重复上述的过程, 知道left与right相遇, 将base值赋给相遇的数组位置. 这时, base值左边的值都是比base值小的. base值右边都是比base值大的. 再分别对两边的两个数组进行快速排序. 就完成了整个数组的有序

public void quickSort(int[] array, int left, int right) {
        
            if (left < right) {
        
                //调整数组, 并找到基准值的位置
                int mid = division(array,left,array.length-1);
                //对分别对左边和右边进行快速排序
                quickSort(array,left,mid-1);
                quickSort(array,mid+1,right);
            }
        }
    
        private int division(int[] array, int left, int right) {
        
            //以最左边的数为基准
            int base = array[left];
            while (left < right) {
        
                //从右边开始向左扫描,直到找到比base小的数
                while (left < right && array[right] >= base) {
        
                    right--;
                }
                //找到了比base小的数, 将其放在left位置
                array[left] = array[right];
                //从左边开始向右扫描, 直到找到比base大的数
                while (left < right && array[left] <= base) {
        
                    left++;
                }
                //找到了比base更大的数, 将其放在right位置
                array[right] = array[left];
            }
            //最后将base放在left位置, 分割结束
            //此时base左边的数都比base小, 右边的数都比它大
            array[left] = base;
            return left;
        }

**优化方案 :**

*  1.选取更合适的**基准值 : \*\* 在上述的例子中我们选取了数组中第一个数为基准值, 实际上如果这个值是数组中的最大值或者最小值, 那么快速排序的效率就会非常低, 所以这里我们可以使用**三数取中**的方法确定基准值. 所谓三数取中就是在最左边, 最右边 和中间的三个数中取出一个中间值作为基准值. 但是, 如果使用了三数取中法, 我们每次找到比比base大或小的数时, 就得将其**left与right上的值交换\*\*, 而不是直接赋值.
 *  2.使用尾递归, 在quickSort()的代码中, 我们这样使用快速排序
    
        public void quickSort(int[] array, int left, int right) {
              
                while (left < right) {
              
                    //调整数组, 并找到基准值的位置
                    int mid = division(array,left,array.length-1);
                    //对分别对左边和右边进行快速排序
                    quickSort(array,left,mid-1);
                    left = mid+1;
                }
            }
    
    这就是对快速排序进行尾递归的优化. 因为每次递归调用都会耗费一定的栈空间, 如果能减少递归, 将会提高性能. 使用迭代而不是递归的方法可以缩减堆栈的深度, 提高整体性能

<table> 
 <thead> 
  <tr> 
   <th>参数</th> 
   <th>结果</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>排序方法</td> 
   <td>快速排序</td> 
  </tr> 
  <tr> 
   <td>平均时间复杂度</td> 
   <td>O(NlogN)</td> 
  </tr> 
  <tr> 
   <td>空间复杂度</td> 
   <td>O(NlogN)</td> 
  </tr> 
  <tr> 
   <td>稳定性</td> 
   <td>不稳定</td> 
  </tr> 
 </tbody> 
</table>

### 3.插入排序 ###

插入排序 : 每一趟将一个待排序的记录, 按照其关键字的大小插入到有序队列的合适位置里, 直到全部插入完成

**基本思想 :** 从数组第一个元素开始, 假设其是有序的, 然后将第二个数按关键字排序插入到第一个元素的左边或右边, 那么前两个数就是有序的了. 继续从第三个数开始, 从后向前扫描, 将其插入在合适的位置, 知道插入数组中最后一个元素, 排序完成

public void insertSort(int[] array) {
        
            for (int i = 1; i < array.length; ++i) {
        
                int j = 0;
                int tmp = array[i];
                for (j = i-1; j >=0 && tmp < array[j]; --j) {
        
                    array[j+1] = array[j];
                }
                array[j+1] = tmp;
            }
        }

<table> 
 <thead> 
  <tr> 
   <th>参数</th> 
   <th>结果</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>排序方法</td> 
   <td>直接插入排序</td> 
  </tr> 
  <tr> 
   <td>平均时间复杂度</td> 
   <td>O(N^2)</td> 
  </tr> 
  <tr> 
   <td>空间复杂度</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>稳定性</td> 
   <td>稳定</td> 
  </tr> 
 </tbody> 
</table>

### 4.希尔排序 ###

希尔排序又称为**缩小增量排序**, 是一种插入排序.

**基本思想 :** 把记录按步长gap分组, 即间距为gap的数组中的数据作为一组, 将每组记录按照直接插入排序的方法进行排序

随着步长逐步减小, 所分的组包含的记录就越多吗当步长的值减小到1时, 整个数据合成一组, 构成一组有序记录, 则完成排序. 所以希尔排序是一个将数组逐渐变得有序的过程

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dpbnRlcnNoaWk_size_16_color_FFFFFF_t_70 1]

public void shellSort(int[] array) {
        
            int gap = array.length / 2;
            while (1 <= gap) {
        
                for (int i = gap; i < array.length; ++i) {
        
                    int j = 0;
                    int tmp = array[i];
                    for (j = i - gap; j >= 0 && tmp < array[j]; j -= gap) {
        
                        array[j + gap] = array[j];
                    }
                    array[j + gap] = tmp;
                }
                gap = gap / 2;
            }
        }

<table> 
 <thead> 
  <tr> 
   <th>参数</th> 
   <th>结果</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>排序方法</td> 
   <td>希尔排序</td> 
  </tr> 
  <tr> 
   <td>平均时间复杂度</td> 
   <td>O(NlogN)</td> 
  </tr> 
  <tr> 
   <td>空间复杂度</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>稳定性</td> 
   <td>不稳定</td> 
  </tr> 
 </tbody> 
</table>

### 5.选择排序 ###

每趟从待排的记录中找到最大或者最小的记录, 并顺序放在已排记录序列末尾, 直到全部排序结束为止

基本思想 :

*  1.从待排序列中, 找到关键字最小的元素
 *  2.如果最小元素不是待排序列的第一个元素, 将其和第一个元素互换
 *  3.从余下的元素中找出最小的元素, 重复1,2步, 知道排序结束

public void selectSort(int[] array) {
        
            for (int i = 0; i < array.length - 1; ++i) {
        
                int min = i;
                for (int j = i + 1; j < array.length; ++j) {
        
                    if (array[j] < array[min]) {
        
                        min = j;
                    }
                }
                if (min != i) {
        
                    int tmp = array[i];
                    array[i] = array[min];
                    array[min] = tmp;
                }
            }
        }

<table> 
 <thead> 
  <tr> 
   <th>参数</th> 
   <th>结果</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>排序方法</td> 
   <td>简单选择排序</td> 
  </tr> 
  <tr> 
   <td>平均时间复杂度</td> 
   <td>O(N^2)</td> 
  </tr> 
  <tr> 
   <td>空间复杂度</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>稳定性</td> 
   <td>不稳定</td> 
  </tr> 
 </tbody> 
</table>

### 6.堆排序 ###

在介绍堆排序之前, 我们先要知道什么是堆

堆 : 堆是一个顺序存储的**完全二叉树**, 每个节点的关键字都不大于其孩子节点的关键字, 这样的堆称为小顶堆. 每个节点的关键字都不小于其孩子节点的关键字, 这样的堆称之为大顶堆.

因为是顺序存储的, 所以我们可以发现其数组元素下标存在以下关系 :

//小顶堆
    arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+2];
    //大顶堆
    arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2];

**算法思想 :**

*  1.首先按堆的定义将数组R\[0…n\]调整为堆(这个过程叫做初始化堆), 交换R\[0\]和R\[n\];
 *  2.然后将R\[0…n-1\]调整为堆, 交换R\[0\]和R\[n-1\];
 *  3.如此反复, 知道交换了R\[0\]和R\[1\]为止

其实就是 : 根据初始数组去构造堆, 然后每次交换第一个和最后一个元素, 输出最后一个元素, 然后把剩下的元素重新调整成大顶堆

public void heapSort(int[] array) {
        
            //初始化数组为堆
            for (int i = array.length/2; i >= 0; --i) {
        
                heapAdjust(array,i,array.length);
            }
    
            for (int i = array.length-1; i > 0; --i) {
        
                //交换最后一个位置和第一个位置(最大值)
                int tmp = array[0];
                array[0] = array[i];
                array[i] = tmp;
    
                heapAdjust(array,0,i);
            }
        }
    
        private void heapAdjust(int[] array, int parent, int length) {
        
            int tmp = array[parent];
            int child = parent * 2 + 1;
            while (child < length) {
        
                //如果有右孩子节点, 并且右孩子节点的值大于左孩子节点, 则选取右孩子节点
                if (child + 1 < length && array[child] < array[child+1]) {
        
                    child++;
                }
                //如果父节点的值已经大于孩子节点的值, 则直接结束
                if (tmp >= array[child]) {
        
                    break;
                }
                //给父节点赋值
                array[parent] = array[child];
    
                //更新parent和child, 继续向下筛选
                parent = child;
                child = 2 * child + 1;
            }
            array[parent] = tmp;
        }

<table> 
 <thead> 
  <tr> 
   <th>参数</th> 
   <th>结果</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>排序方法</td> 
   <td>堆排序</td> 
  </tr> 
  <tr> 
   <td>平均时间复杂度</td> 
   <td>O(NlogN)</td> 
  </tr> 
  <tr> 
   <td>空间复杂度</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>稳定性</td> 
   <td>不稳定</td> 
  </tr> 
 </tbody> 
</table>

### 7.归并排序 ###

归并排序是建立在归并操作上的一种有效的算法, 采用了分治思想. 将已有序的子序列合并, 得到完全有序的序列; 即先使每个子序列有序, 再使子序列间断有序, 若将两个有序表合并成一个有序表, 称为二路归并

**算法思想 :**

将记录分成gap(初始为1)长度的子序列, 再将相邻的子序列合并成有序. 然后gap乘2, 继续合并, 直到整个数组有序

public void mergeSort(int[] array) {
        
            //
            for (int gap = 1; gap <= array.length; gap *= 2) {
        
                mergePass(array, gap, array.length);
            }
        }
    
        private void mergePass(int[] array, int gap, int length) {
        
            int i = 0;
    
            //归并gap长度的两个相邻子表
            for (i = 0; i + 2*gap - 1 < length; i += 2*gap) {
        
                merge(array, i, i + gap -1, i + 2 * gap - 1);
            }
    
            //剩余两个子表, 后者长度小于gap
            if (i + gap - 1 < length) {
        
                merge(array, i, i + gap - 1, length - 1);
            }
    
        }
    
        private void merge(int[] array, int left, int mid, int right) {
        
            //第一个数组中的指针
            int i = left;
            //第二个数组中的指针
            int j = mid + 1;
            //新开辟数组的指针
            int k = 0;
            int[] array2 = new int[right-left+1];
    
            while (i <= mid && j <= right) {
        
                if (array[i] <= array[j]) {
        
                    array2[k++] = array[i++];
                } else {
        
                    array2[k++] = array[j++];
                }
            }
            while (i <= mid) {
        
                array2[k++] = array[i++];
            }
    
            while (j <= right) {
        
                array2[k++] = array[j++];
            }
    
            for (k = 0, i = left; i <= right; ++i,++k) {
        
                array[i] = array2[k];
            }
        }

<table> 
 <thead> 
  <tr> 
   <th>参数</th> 
   <th>结果</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>排序方法</td> 
   <td>归并排序</td> 
  </tr> 
  <tr> 
   <td>平均时间复杂度</td> 
   <td>O(NlogN)</td> 
  </tr> 
  <tr> 
   <td>空间复杂度</td> 
   <td>O(N)</td> 
  </tr> 
  <tr> 
   <td>稳定性</td> 
   <td>稳定</td> 
  </tr> 
 </tbody> 
</table>

**堆排序, 快速排序, 归并排序三者的优缺点 :**

*  1.若从空间复杂度来考虑, 首选堆排序, 再是快速排序, 最后是归并排序
 *  2.若从稳定性来考虑, 应选取归并排序, 快速排序和堆排序都是不稳定的
 *  3.平均情况下的排序速度考虑, 选择快速排序

### 8.基数排序 ###

基数排序与前面的其中排序方法都是一样, 它不需要比较关键字的大小

它是根据关键字中各位的值, 通过对排序的N个元素进行若干趟"分配与收集"来实现排序的

每个数的个位上基数都是由0~9表示的, 给0-9分配十个桶, 将数据按其个位的不同放在每个桶里, 这样整组数据就是个位有序的. 紧接着是十位, 百位…最后就能的到排序完成的序列

<table> 
 <thead> 
  <tr> 
   <th>参数</th> 
   <th>结果</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>排序方法</td> 
   <td>基数排序</td> 
  </tr> 
  <tr> 
   <td>平均时间复杂度</td> 
   <td>O(n+r)</td> 
  </tr> 
  <tr> 
   <td>空间复杂度</td> 
   <td>O(n+r)</td> 
  </tr> 
  <tr> 
   <td>稳定性</td> 
   <td>稳定</td> 
  </tr> 
 </tbody> 
</table>

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dpbnRlcnNoaWk_size_16_color_FFFFFF_t_70]: /images/20211108/4702649c20ed46079578b18fc49e0bb0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dpbnRlcnNoaWk_size_16_color_FFFFFF_t_70 1]: /images/20211108/3e163cc717514437ac0f1073a645acdf.png