各种排序算法比较

浅浅的花香味﹌ 2022-08-01 03:13 212阅读 0赞

# 1 排序的稳定性 #

## (1) 稳定的排序 ##

<table> 
 <thead> 
  <tr> 
   <th align="left">稳定的排序</th> 
   <th align="left">时间复杂度</th> 
   <th>空间复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">冒泡排序(bubble sort)</td> 
   <td align="left">最差，平均都是O(n^2),最好是O(n)</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td align="left">鸡尾酒排序(Cocktail sort,双向冒泡排序)</td> 
   <td align="left">最差，平均都是O(n^2),最好是O(n)</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td align="left">插入排序(insertion sort)</td> 
   <td align="left">最差，平均都是O(n^2),最好是O(n)</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td align="left">归并排序(merge sort)</td> 
   <td align="left">最差，平均，最好都是O(nlogn)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td align="left">桶排序(bucket sort)</td> 
   <td align="left">O(n)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td align="left">基数排序(radix sort)</td> 
   <td align="left">O(dn)(d是常数)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td align="left">二叉树排序(Binary sort)</td> 
   <td align="left">O(nlogn)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td align="left">图书馆排序(Library sort)</td> 
   <td align="left">O(nlogn)</td> 
   <td>(1+ε)n</td> 
  </tr> 
 </tbody> 
</table>

## (2) 不稳定的排序 ##

<table> 
 <thead> 
  <tr> 
   <th align="left">不稳定的排序</th> 
   <th align="left">时间复杂度</th> 
   <th>空间复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">选择排序(selection sort)</td> 
   <td align="left">最差，平均都是O(n^2</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td align="left">希尔排序(shell sort)</td> 
   <td align="left">O(nlogn)</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td align="left">堆排序(heap sort)</td> 
   <td align="left">最差，平均，最好都是O(nlogn)</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td align="left">快速排序(quick sort)</td> 
   <td align="left">平均是O(nlogn)最坏是O(n^2)</td> 
   <td>O(logn)</td> 
  </tr> 
 </tbody> 
</table>

# 2 各种排序 #

## (1) 冒泡排序 ##

### 具体算法 ###

void BubbleSort(SeqList R){ //R(1..n)是带排序序列，采用自下向上的扫描，对R做冒泡排序；
        int i,j;
        Boolean exchange;   //交换标志；
        for(i=1;i<n;i++){
            exchange=false;     //最多做n-1次排序；
            for(j=n-1;j>=i;j--){    //对当前无序区自下而上扫描；
                if(R[j+1].key<R[j].key){
                    R[0]=R[j+1];
                    R[j+1]=R[j];
                    R[j]=R[0];
                    exchange=true;
                }
            }
            if(!exchange){  //本次排序没发生交换，提前终止算法
                return;
            }
        }
    }

### 程序举例 ###

输入10个整数，输出排序结果：

public class Test { 
        public static void bubbleSort(int[] source) {
            for (int i = source.length - 1; i > 0; i--) {
                for (int j = 0; j < i; j++) {
                    if (source[j] > source[j + 1])
                        swap(source, j, j + 1);
                }
            }
        }
    
        private static void swap(int[] source, int x, int y) {
            int temp = source[x];
            source[x] = source[y];
            source[y] = temp;
        }
    
        public static void main(String[] args) {
            int[] a = { 4, 2, 1, 6, 3, 6, 8, 9, 4, 0 };
            int i;
            bubbleSort(a);
            for (int b : a) {
                System.out.print(b + " ");
            }
        }
    }

### 算法分析 ###

最好情况下的时间复杂度：初始文件是正序的，

*  比较次数：Cmin=n-1；
 *  移动次数：Mmin=0；

所以冒泡排序的最好的时间复杂度是O(n);

最坏情况下的时间复杂度：初始文件是反序的，要进行n-1次排序，每次排序要进行n-i次比较，每次比较都要进行交换记录（3次位置移动），

*  比较次数：Cmax=n(n-1)/2=O(n^2)；
 *  移动次数：Mmax=3n(n-1)/2=O(n^2)；

所以冒泡排序最坏的时间复杂度为O(n^2);  
平均的时间复杂度是O(n^2)。

## (2) 选择排序 ##

### 算法思想： ###

首先在为排序序列中找到最小元素，放到排序序列起始位置。然后再从剩余未排序元素中找到最小元素，放到排序序列末尾。以此类推，直到全部元素都排序完成。

### 程序举例 ###

输入10个整数，输出排序结果：

public class Test { 
        public static void selectSort(int[] source) {
            for (int i = 0; i < source.length; i++) {
                for (int j = i + 1; j < source.length; j++) {
                    if (source[i] > source[j]) {
                        swap(source, i, j);
                    }
                }
            }
        }
    
        private static void swap(int[] source, int x, int y) {
            int temp = source[x];
            source[x] = source[y];
            source[y] = temp;
        }
    
        public static void main(String[] args) {
            int[] a = { 4, 2, 1, 6, 3, 6, 8, 9, 4, 0 };
            int i;
            selectSort(a);
            for (int b : a) {
                System.out.print(b + " ");
            }
        }
    }

## (3)插入排序 ##

### 算法思想 ###

*  从第一个元素开始，该元素被认为已经排序；
 *  取出下一个元素，在已经排序的元素中**从后向前**扫描；
 *  如果以排序元素大于新元素，就像后移动；
 *  重复步骤3，直到找到以排序元素小于或等于新元素的位置；
 *  将新元素插入到已排序序列中；
 *  重复步骤2.

### 程序举例 ###

public class Test { 
        public static void selectSort(int[] source) {
            for (int i = 1; i < source.length; i++) {
                for (int j = i; (j > 0) && (source[j] < source[j - 1]); j--) {
                    swap(source, j, j - 1);
                }
            }
        }
    
        private static void swap(int[] source, int x, int y) {
            int temp = source[x];
            source[x] = source[y];
            source[y] = temp;
        }
    
        public static void main(String[] args) {
            int[] a = { 4, 2, 1, 6, 3, 6, 8, 9, 4, 0 };
            int i;
            selectSort(a);
            for (int b : a) {
                System.out.print(b + " ");
            }
        }
    }

### 算法分析 ###

*  最好情况下，序列本身是升序排列，这时只需要进行n-1次比较；
 *  最坏情况下，序列是降序排列，比较n(n-1)/2次，赋值操作是比较操作的次数加上n-1次，
 *  平均时间复杂度为O(n^2).

插入排序不适合数据量大的排序应用，适合数据量较小时候的操作。

## (4)希尔排序 ##

### 算法思想 ###

*  先取一个小于n的整数d1作为第一个增量，把全部记录分成d1个分组，所有距离为d1的元素在一个组内；
 *  组内排序；
 *  取第二个增量d2

### 算法实现 ###

void ShellPass(SeqList R,int d){
        //希尔排序的一趟排序，d是增量；
        for(int i=d+1;i<n;i++){     //将R[d+1,n]分别插入各组当前的有序区；
            if(R[i].key<R[i-d].key){
                R[0]=R[i];  R[0]只是暂存单元，不是哨兵；
                j=i-d;
                do{
                    R[j+d]=R[j];    //后移记录
                    j=j-d;      //查找前一记录
                }while(j>0 && R[0].key<R[j].key);
                R[j+d]=R[0];    //插入R[i]到正确的位置上；
            }
        }
    }
    
    void ShellSort(SeqList R){
    
        int increment=n;    //增量初值，不妨设n>0;
        do{
            increment=increment/3+1;    //求下一增量；
            ShellPass(R,increment);     //一趟增量为increment的Shell排序；
        }while(increment>1)
    }

### 程序举例 ###

public class Test {
        public static int[] a = { 4, 2, 1, 6, 3, 6, 8, 9, 4, 0 };
    
        public static void main(String[] args) {
            int i;
            int index = a.length;
    
            System.out.println("before sort:");
            for (int b : a) {
                System.out.print(b + " ");
            }
            System.out.println();
    
            ShellSort(index - 1);
    
            System.out.println("after sort: ");
            for (int b : a) {
                System.out.print(b + " ");
            }
            System.out.println();
        }
    
        public static void ShellSort(int index) {
            int i, j, k;
            int temp;
            boolean change;
            int dataLength; // 增量
            int pointer; // 进行处理的位置
    
            dataLength = index / 2;
    
            while (dataLength != 0) {
                for (j = dataLength; j < index; j++) {
                    change = false;
                    temp = a[j];
                    pointer = j - dataLength;
    
                    while (temp < a[pointer] && pointer >= 0 && pointer <= index) {
                        a[pointer + dataLength] = a[pointer];
                        pointer = pointer - dataLength;
                        change = true;
                        if (pointer < 0 || pointer > index)
                            break;
                    }
    
                    a[pointer + dataLength] = temp;
    
                    if (change) {
                        System.out.println("during the sort: ");
                        for (int b : a) {
                            System.out.print(b + " ");
                        }
                        System.out.println();
                    }
                }
                dataLength = dataLength / 2;
            }
        }
    }

## (5)二分排序 ##

### 算法思想 ###

二分法排序（折半查找插入排序）  
跟插入排序类此，只是在查找时采用折半查找的方式。

### 实例程序 ###

public class Test {
        public static void main(String[] args) {
            int[] a = { 4, 2, 1, 6, 3, 6, 8, 9, 4, 0 };
            int i, j;
            int low, high, mid;
            int temp;
            for (i = 1; i < 10; i++) {
                temp = a[i];
                low = 0;
                high = i - 1;
                while (low <= high) {
                    mid = (low + high) / 2;
                    if (a[mid] > temp)
                        high = mid - 1;
                    else
                        low = mid + 1;
                }
                for (j = i - 1; j > high; j--) {
                    a[j + 1] = a[j];
                }
                a[high + 1] = temp;
            }
    
            for (i = 0; i < 10; i++) {
                System.out.print(a[i] + ", ");
            }
        }
    }

### 算法分析 ###

*  比较次数 O(nlogn)
 *  元素移动次数 O(n^2)
 *  复杂度 O(n^2)、
 *  稳定的

## (6)快速排序 ##

### 算法思想 ###

待排序序列为R\[low,high\]，利用分治法的思想进行快速排序：

**快速排序算法：**

1.  分解：选取任意一个记录（一般是第一个）作为基准（Pivot）将当前序列划分为左右两个子区间 R\[low,Piovt-1\],R\[Piovt+1,high\]，使左边的所有记录小于等于基准，右边的记录大于等于基准。此时基准记录就在正确的位置上了。
2.  求解：递归的调用快速排序对左右区间快速排序。
3.  组合：在递归结束后，整个序列实际上已经有许了，所以组合步骤可以视为空操作。

**划分算法Partition**

1.  首先选取第一个记录**R\[i\]**作为基准保存在pivot中；
2.  从后先前扫描，找到第一个小于pivot的记录**R\[j\]**，将**R\[j\]**移至**i**处，交换后**R\[j\]**相当于piovt。
3.  从前向后扫描，找到第一个大于pivot的记录**R\[i\]**，将**R\[i\]**移至**j**处。
4.  重复2，3，直到i=j时，完成一次划分。

### 算法实现 ###

快速排序

void QuickSort(SeqList R,int low,int high){
        int pivot;
        if(low<high){
            pivot=Partition(R,low,high);
            QuickSort(R,low,pivot-1);
            QuickSort(R,pivot+1,high);
        }
    }

划分算法

int Partition(SeqList R ,int i,int j){
        //返回基准记录的位置
        ReceType pivot=R[i];
        while(i<j){
            while(i<j&&R[j].key>=pivot.key)
                j--;    //从右向左扫描，查找第一个小于pivot.key的记录R[j]
            if(i<j)     //表示找到R[j]的关键字<pivot.key
                R[i++]=R[j];    //相当于交换R[i],R[j]交换后i指针加1；
            while(i<j&&R[i].key<=pivot.key)
                i++;
            if(i<j)
                R[j--]=R[i];
        }
        R[i]=pivot;
        return i;
    }

### 示例程序 ###

public class Test{
        public static void sort(int source[],int low,int high){
            int i,j,x;
            if(low<high){
                i=low;
                j=high;
                x=source[i];
                while(i<j){
                    while(i<j&&source[j]>x)
                        j--;
                    if(i<j){
                        source[i]=source[j];
                        i++;
                    }
                    while(i<j&&source[i]<x)
                        i++;
                    if(i<j){
                        source[j]=source[i];
                        j--;
                    }
                }
                source[i]=x;
                sort(source,low,i-1);
                sort(source,i+1,high);
            }
        }
    
        public static void main(String[]args){
            int []a={ 4, 2, 1, 6, 3, 6, 8, 9, 4, 0 };
    
            sort(a,0,a.length-1);
    
            for(int b:a)
                System.out.print(b+", ");
        }
    }

### 算法分析 ###

快速排序是一种不稳定的排序，  
时间复杂度：平均是O(nlogn)，最坏是O(n^2)

## (7)归并排序 ##

### 算法思想 ###

1.  将序列每相邻的两个数字进行归并操作（merge），形成floor（n/2）个序列，排序后每个序列包含2个元素；
2.  将上述序列再次归并，形成floor（n/4）个序列，每个序列有4个元素；
3.  重复2，知道所有元素排序完成。

### 示例代码 ###

public class Test {
        public static void merge(int array[], int start1, int end1, int start2,
                int end2) {
            int i, j; // 分别为表1和表2上的游标
            {
                i = start1;
                j = start2;
            }
            int k = 0;
            int[] temp = new int[end2 - start1 + 1]; // 建立一个长度为2个列表长度之和的临时数组
    
            while (i <= end1 && j <= end2) {
                if (array[i] > array[j])
                    temp[k++] = array[j++];
                else
                    temp[k++] = array[i++];
            }
            // 将剩下的元素依次放入临时数组中
            while (i <= end1)
                temp[k++] = array[i++];
            while (j <= end2)
                temp[k++] = array[j++];
            k = start1;
            for (int element : temp)
                // 将临时数组复制到原数组
                array[k++] = element;
        }
    
        public static void mergeSort(int array[], int start, int end) {
            if (start < end) {
                int mid = (start + end) / 2;
    
                mergeSort(array, start, mid);
                mergeSort(array, mid + 1, end);
    
                merge(array, start, mid, mid + 1, end);
    
                /* * int mid=(start+end)/4; * * mergeSort(array,start,1*mid); mergeSort(array,1*mid+1,2*mid); * mergeSort(array,2*mid+1,3*mid); mergeSort(array,3*mid+1,end); * * merge(array,start,1*mid,1*mid+1,2*mid); * merge(array,2*mid+1,3*mid,3*mid+1,end); * merge(array,start,2*mid,2*mid+1,end); */
            }
        }
    
        public static void main(String[] args) {
            int[] a = { 4, 2, 1, 6, 3, 6, 8, 9, 4, 0 };
            mergeSort(a, 0, a.length - 1);
            for (int b : a) {
                System.out.print(b + ", ");
            }
        }
    }

### 算法分析 ###

归并排序的最差、平均、最好时间复杂度都是O(nlogn)，但是他需要额外的存储空间。