八种排序算法总结

心已赠人 2021-09-17 09:26 337阅读 0赞

8种基本排序情况概述：

1、稳定性

归并排序、冒泡排序、插入排序、基数排序是稳定的

选择排序、快速排序、希尔排序、堆排序是不稳定的

2、时间复杂度

最基础的四个算法：冒泡、选择、插入、快排中，快排的时间复杂度最小O(n\*log2n)，其他都是O（n2）

<table> 
 <tbody> 
  <tr> 
   <td>排序法</td> 
   <td>平均时间</td> 
   <td>最差情形</td> 
   <td>稳定度</td> 
   <td>额外空间</td> 
   <td>备注</td> 
  </tr> 
  <tr> 
   <td>冒泡</td> 
   <td>O(n2)</td> 
   <td>&nbsp;&nbsp;&nbsp; O(n2)</td> 
   <td>稳定</td> 
   <td>O(1)</td> 
   <td>n小时较好</td> 
  </tr> 
  <tr> 
   <td>选择</td> 
   <td>O(n2)</td> 
   <td>O(n2)</td> 
   <td>不稳定</td> 
   <td>O(1)</td> 
   <td>n小时较好</td> 
  </tr> 
  <tr> 
   <td>插入</td> 
   <td>O(n2)</td> 
   <td>O(n2)</td> 
   <td>稳定</td> 
   <td>O(1)</td> 
   <td>大部分已排序时较好</td> 
  </tr> 
  <tr> 
   <td>基数</td> 
   <td>O(logRB)</td> 
   <td>O(logRB)</td> 
   <td>稳定</td> 
   <td>O(n)</td> 
   <td> <p>B是真数(0-9)，</p> <p>R是基数(个十百)</p> </td> 
  </tr> 
  <tr> 
   <td>Shell</td> 
   <td>O(nlogn)</td> 
   <td>O(ns) 1&lt;s&lt;2</td> 
   <td>不稳定</td> 
   <td>O(1)</td> 
   <td>s是所选分组</td> 
  </tr> 
  <tr> 
   <td>快速</td> 
   <td>O(nlogn)</td> 
   <td>O(n2)</td> 
   <td>不稳定</td> 
   <td>O(nlogn)</td> 
   <td>n大时较好</td> 
  </tr> 
  <tr> 
   <td>归并</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>稳定</td> 
   <td>O(1)</td> 
   <td>n大时较好</td> 
  </tr> 
  <tr> 
   <td>堆</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>不稳定</td> 
   <td>O(1)</td> 
   <td>n大时较好</td> 
  </tr> 
 </tbody> 
</table>

**直接插入排序**：插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。刚开始这个小序列只包含第一个元素，事件复杂度O(n2)。比较是从这个小序列的末尾开始的。想要插入的元素和小序列的最大者开始比起，如果比它大则直接插在其后面，否则一直往前找它该插入的位置。如果遇见了一个和插入元素相等的，则把插入元素放在这个相等元素的后面。所以相等元素间的顺序没有改变，是稳定的。（使用场景：把新的数据插入到已经排好的数据列中）

1.  将第一个数和第二个数排序，然后构成一个有序序列
2.  将第三个数插入进去，构成一个新的有序序列。
3.  对第四个数、第五个数……直到最后一个数，重复第二步

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfc2h1eXU_size_16_color_FFFFFF_t_70][]

java代码实现

1.  设定插入次数，即循环次数，但是第一个数字不用排序，所以一共循环数组长度-1次，for(int i=1;i<length;i++)；
2.  设定插入数=insertNum和得到已经排好序列的最后一个数的位数j=i-1。
3.  从已经排好序列的最后一个数开始向前循环，如果要插入数小于当前数insertNum<a\[j\]，就将当前数向后移动一位。
4.  将当前数放置到空着的位置，即j+1。

public class InsertSort {
    
        public void insertSort(int[] a){
            int length=a.length;//数组长度，将这个提取出来是为了提高速度。
            int insertNum;//要插入的数
            for(int i=1;i<length;i++){//插入的次数
                insertNum=a[i];//要插入的数
                int j=i-1;//已经排序好的序列元素个数
                while(j>=0&&a[j]>insertNum){//序列从后到前循环，将大于insertNum的数向后移动一格
                    a[j+1]=a[j];//元素移动一格
                    j--;
                }
                a[j+1]=insertNum;//将需要插入的数放在要插入的位置。
            }
        }
    }

**冒泡排序**:是相邻元素之间的比较和交换，两重循环O(n2)；所以，如果两个相邻元素相等，是不会交换的。所以它是一种稳定的排序方法,冒泡排序是最慢的排序算法，实际运用中效率最低，当数列为由小到大的有序数列时为最好情况，当由大到小时为为最坏情况。（很少使用）

1.  将序列中所有元素两两比较，将最大的放在最后面。
2.  将剩余序列中所有元素两两比较，将最大的放在最后面。
3.  重复第二步，直到只剩下一个数。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfc2h1eXU_size_16_color_FFFFFF_t_70 1][]

java实现：

1.  设置循环次数。
2.  设置开始比较的位数，和结束的位数。
3.  两两比较，将最小的放到前面去。
4.  重复2、3步，直到循环次数完毕。

public class BubbleSort {
        public void bubbleSort(int[] a){
            int length=a.length;//数组长度
            int temp;
            for(int i=0;i<a.length;i++){
                for(int j=0;j<a.length-i-1;j++){
                    if(a[j]>a[j+1]){
                        temp=a[j];
                        a[j]=a[j+1];
                        a[j+1]=temp;
                    }
                }
            }
        }
    }

未完待续

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfc2h1eXU_size_16_color_FFFFFF_t_70]: /images/20210901/8f07c92c7d4f4e0ca728ba195a224736.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfc2h1eXU_size_16_color_FFFFFF_t_70 1]: /images/20210901/4604945bbea645bd817cad1ac909caca.png