排序算法再总结再分析java版---未完待续

比眉伴天荒 2022-07-15 14:55 188阅读 0赞

# 概述 #

排序大的分类可以分为两种：内排序和外排序。在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。下面讲的排序都是属于内排序。

内排序有可以分为以下几类：

(1)、插入排序：直接插入排序、二分法插入排序、希尔排序。

思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置，直到全部插入排序完为止。

(2)、选择排序：简单选择排序、堆排序。

思想：每趟从待排序的记录序列中选择关键字最小的记录放置到已排序表的最前位置，直到全部排完。

(3)、交换排序：冒泡排序、快速排序。

思想：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较 小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

(4)、归并排序

(5)、基数排序

# 算法 #

## 直接插入排序 ##

**1)基本思想：**

每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。

**2)图解：**

![24160822-d0957aa2ca8a4500bfc84dbf36865578.png][]

**3)时间复杂度：**

最好O(n)------最坏O(n2)-------平均O(n2)

直接插入排序耗时的操作有：比较+后移赋值。时间复杂度如下：

a)最好情况：序列是升序排列，在这种情况下，需要进行的比较操作需（n-1）次。后移赋值操作为0次。即O(n)

b)最坏情况：序列是降序排列，那么此时需要进行的比较共有[n(n-1)/2][n_n-1_2]次。后移赋值操作是比较操作的次数加上 (n-1）次。即O(n^2)

**4)空间复杂度：**O(1)

从实现原理可知，直接插入排序是在原输入数组上进行后移赋值操作的（称“就地排序”），所需开辟的辅助空间跟输入数组规模无关，所以空间复杂度为： O(1)

**5)是否稳定：稳定**

**6)延伸：**

快速排序（不使用随机化）是否一定比插入排序快？

答：不一定，当输入数组已经排好序时，插入排序需要O(n)时间，而快速排序需要O(n^2)时间。

**7)源码：**

package com.apple.sort;
 /**
 * 插入排序
 * 直接插入排序
 * 
 * @date 2016年8月1日
 * @author tianjinsong
 */
 public class InsertSort {
 
     public static void main(String[] args) {
         int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23, 34,15,35,25,53,51};   
         InsertSort.sort( a, a.length);
         for(int i=0;i<a.length;i++){   
             System.out.print(a[i] + ",");   
         }   
     }
 
 
     static void sort(int a[], int n) {
         int i, j;
         int temp;
         for (i = 1; i < n; i++){
             for (j = i - 1; j >= 0 && a[j] > a[j + 1]; j--){
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j+1] = temp;
             }
         }
     }
 
 
 }

## 二分法插入排序 ##

**1)基本思想：**

二分法插入排序的思想和直接插入一样，只是找合适的插入位置的方式不同，这里是按二分法找到合适的位置，可以减少比较的次数。

**2)图解：**

![24162933-28ad5af710d8441d97ee22fddb873a84.jpg][]

**3)时间复杂度：**

最好O(n)------最坏O(n2)-------平均O(n2)

二分查找插入位置，因为不是查找相等值，而是基于比较查插入合适的位置，所以必须查到最后一个元素才知道插入位置。二分查找最坏时间复杂度：当2^X>=n时，查询结束，所以查询的次数就为x，而x等于log2n（以2为底，n的对数）。即O(log2n)所以，二分查找排序比较次数为：x=log2n

二分查找插入排序耗时的操作有：比较 + 后移赋值。时间复杂度如下：

a)最好情况：查找的位置是有序区的最后一位后面一位，则无须进行后移赋值操作，其比较次数为：log2n 。即O(log2n)

b)最坏情况：查找的位置是有序区的第一个位置，则需要的比较次数为：log2n，需要的赋值操作次数为[n(n-1)/2][n_n-1_2]加上 (n-1) 次。即O(n^2)

**4)空间复杂度：**O(1)

从实现原理可知，二分查找插入排序是在原输入数组上进行后移赋值操作的（称“就地排序”），所需开辟的辅助空间跟输入数组规模无关，所以空间复杂度为：O(1)

**5)是否稳定：稳定**

**6)源码：**

package com.apple.sort;
 /**
 * 插入排序
 * 二分法插入排序
 * @date 2016年8月2日
 * @author 
 */
 public class HalfInsertSort {
 public static void main(String[] args) {
 int[] a={49,38,65,97,176,213,227,49,78,34,12,164,11,18,1};
 System.out.println("排序之前：");
 for (int i = 0; i < a.length; i++) {
 System.out.print(a[i]+" ");
 }
 //二分插入排序
 sort(a);
 System.out.println();
 System.out.println("排序之后：");
 for (int i = 0; i < a.length; i++) {
 System.out.print(a[i]+" ");
 }
 }
 
 private static void sort(int[] a) {
 for (int i = 1; i < a.length; i++) {//从第二个元素循环无序数组
 int temp = a[i]; //要比较的值
 int left = 0;
 int right = i-1;
 int mid = 0;
 while(left<=right){ //循环找到left
 mid = (left+right)/2;
 if(temp<a[mid]){
 right = mid-1;
 }else{
 left = mid+1;
 }
 }
 for (int j = i-1; j >= left; j--) { //将left右边无素全部右移一位
 a[j+1] = a[j];
 }
 //给left赋值,
 a[left] = temp;
 }
 }
 }

## 希尔排序 ##

**1)基本思想：**

分治策略，希尔排序是一种分组直接插入排序方法，其原理是：先将整个序列分割成若干小的子序列，再分别对子序列进行直接插入排序，使得原来序列成为基本有序。这样通过对较小的序列进行插入排序，然后对基本有序的数列进行插入排序，能够提高插入排序算法的效率。

**2)图解：**

![24164131-db4877dab9c94b63bcfb2cdf7f9cbf69.png][]

**3)时间复杂度：**

O([nlogn][]) > O(n的l.25到1.6次方) > O(n2)

希尔排序的时间复杂度与增量的选取有关， 希尔排序没有[快速排序算法][Link 1]快 O(nlogn)，因此中等大小规模表现良好，对规模非常大的[数据排序][Link 2]不是最优选择。但是比O(n²)复杂度的算法快得多。

**4)空间复杂度：**O(1)

从实现原理可知，希尔排序是在原输入数组上进行后移赋值操作的（称“就地排序”），所需开辟的辅助空间跟输入数组规模无关，所以空间复杂度为：O(1)

**5)是否稳定：不稳定**

**6)源码：**

package com.apple.sort;
 /**
 * 插入排序
 * 希尔排序
 * @date 2016年8月1日
 * @author tianjinsong
 */
 public class ShellSort {
 
 public static void main(String[] args) {
 int a[]={1,54,6,3,78, 34, 12,45,56,100}; 
 ShellSort.sort(a, a.length);
 }
 
 static void sort(int a[], int n){
 int i, j, gap;
 int temp;
 for (gap = n / 2; gap > 0; gap /= 2){ //步长
 for (i = gap; i < n; i++){ 
 for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap){ //每个元素与自己组内的数据进行直接插入排序
 temp = a[j];
 a[j] = a[j + gap];
 a[j + gap] = temp;
 }
 }
 }
 }
 
 }

## 简单选择排序 ##

**1)基本思想：**

在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

**2)图解：**

![24170221-5e84d6b12ea545618b673783789b5803.png][]

**3)时间复杂度：**

最好O(n2)------最坏O(n2)-------平均O(n2)

**4)空间复杂度：** O(1)

**5)是否稳定：不稳定**

**6)源码：**

package com.apple.sort;
 /**
 * 选择排序 
 * .简单选择排序 
 * @date 2016年8月1日
 * @author tianjinsong
 */
 public class SelectSort {
 
 public static void main(String[] args) {
 int a[]={1,54,6,3,78,34,12,45}; 
 SelectSort.selectSort(a, a.length);
 for(int i=0;i<a.length;i++) 
 System.out.println(a[i]); 
 }
 
 public static void selectSort(int[] a, int n){ 
 int position=0; 
 for(int i = 0; i < n; i++){ 
 position=i; 
 int temp=a[i]; 
 for(int j = i+1;j < n; j++){ 
 if(a[j]<temp){ 
 temp=a[j]; 
 position=j; 
 } 
 } 
 a[position]=a[i]; 
 a[i]=temp; 
 } 
 } 
 
 }

## 堆排序 ##

**1)基本思想：**

堆排序是一种树形选择排序，是对直接选择排序的有效改进。

初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个 堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对 它们作交换，最后得到有n个节点的有序序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。

**2)图解：**

**a.****什么是堆**

首先堆是一种[数据结构][Link 3]，是一棵完全二叉树且满足性质：所有非叶子结点的值均不大于或均不小于其左、右孩子结点的值，如下是一个堆得示例：

![0_1315782402S22O.gif][]

9>8,9>5;8>3,8>1;5>2 由此发现非叶子结点的值均不小于左右孩子结点的值，所以这是个大顶堆，即堆顶的值是这个堆中最大的一个。

下面的问题是我们怎么样在计算机中存储这个堆呢？也许有人会想到树的存储，确实，刚看这个堆我也是这么想的。然而事实并非如此，这个堆可以看成是一个一维数组A\[6\]=\{9,8,5,3,1,2\}，那么相应的这个数组需满足性质：A\[i\]<=A\[2\*i\] && A\[i\]<=A\[2\*i+1\] 。其中A\[i\]对应堆中的非叶子结点，A\[2\*i\]和A\[2\*i+1\]对应于左右孩子结点。并且最后一非叶子结点下标为\[n/2\]向下取整。

为什么是\[n/2\]向下取整呢？在这里我简单的说明一下：设n1表示完全二叉树中有一个孩子的结点，n2表示表示完全二叉树中有两个孩子的结点，d表示非叶子结点的个数，那么总的结点个数：n=n1+2\*n2+1。

（1）当n为奇数时，n1=0，n2=(n-1)/2，d=n2+n1=(n-1)/2

（2）当n为偶数时，n1=1，n2=n/2-1，d=n2+n1=n/2

由此可以看出d=\[n/2\]向下取整.

注：请大家一定要结合完全二叉树形式的堆以及堆的数组存储形式来看下面的内容，这样才能真正理解堆排序的过程及其本质。

**b.筛选法调整堆**

（1）引出：

现给定一个大顶堆：![0_1315782402S22O.gif][] 即：A\[6\]=\{9,8,5,3,1,2\}，如果我们稍做破坏，把9跟2互换，同时把a\[6\]这个结点从堆中去掉，于是得到下面这个完全二叉树：

![0_1315782894Vxz8.gif][] A\[5\]=\{2,8,5,3,1\}

显然它不是一个堆，那我们怎么把它调整为一个堆呢？首先观察，我们只是改变了根结点的值，所以根结点左、右子树均是大顶堆。其次思考，既然是根结点可能破坏了堆的性质，那我们就可以把根结点往下沉，让最大值网上浮，即比较根结点和左、右孩子的值，若根结点的值不小于孩子结点的值，说明根结点并没有破坏堆的性质，不用调整；若根结点的值小于左右孩子结点中的任意一个值，则根结点与孩子结点中较大的一个互换，互换之后又可能破坏了左或右子树的堆性质，于是要对子树进行上述调整。这样的一次调整我们称之为一次筛选。

（2）代码：

//堆调整，使其生成最大堆 
 private static void maxHeap(int[] data, int parentIndex) { 
 int lastIndex = data.length -1;
 int left,right,largest; 
 largest=left=2 * parentIndex + 1; 
 
 // 如果左子节点大于父节点，则将左子节点作为最大节点 
 if (left > lastIndex) { 
 return;
 } 
 right = left + 1;
 // 如果右子节点比最大节点还大，那么最大节点应该是右子节点 
 if(right<=lastIndex && data[right] > data[left]){ 
 largest=right; 
 } 
 
 if(data[largest] > data[parentIndex] ){//根结点的值不是最大时,交换a[i]，a[largest] 
 swap(data, largest, parentIndex);
 //自上而下调整堆 
 maxHeap(data, largest); 
 } 
 }

（3）示例

> 以这个完全二叉树为例 ： ![0_1315782894Vxz8.gif][] A\[5\]=\{2,8,5,3,1\}
> 
> 第一次筛选：2和8交换
> 
> ![0_1315784489Yw4n.gif][] A\[5\]=\{ 8,2,5,3,1\}  
> 
> 
> 第二次筛选：2和3交换
> 
> ![0_1315784510fuuq.gif][] A\[5\]=\{8,3,5,2,1\}
> 
> 筛选完毕，得到大顶堆A\[5\]=\{8,3,5,2,1\}。
> 
> （4）时间代价分析
> 
> 每一次筛选的过程就是调用一次maxHeap函数，需要的时间是O（1）。那么要执行多少次筛选呢？从上述中可以看出，每一次筛选根结点都往下沉，所以筛选次数不会超过完全二叉树的深度：（\[log**2**n\]向下取整+1），其中n为结点个数,2为底数,即时间复杂度为O（log**2**n）
> 
>  为什么n个结点的完全二叉树的深度是(\[log**2**n\]向下取整+1)呢？这里给出简单的说明：

深度为h的完全二叉树至多有2^h-1个结点，即2^(h-1)<=n<2^h,推出h-1<=log**2**n<h;由于h是一个整数，所以h=\[log**2**n\]向下取整+1 .

**c.建堆**

b中叙述了堆的筛选过程，但是给定一个待排序的序列，怎样通过筛选使这个序列满足堆的性质呢？

给定待排序序列![0_1315787970NpMp.gif][] A\[6\]=\{3,5,8,9,1,2\},怎样使它变成一个堆呢？

仔细想一想筛选法的前提条件是什么：根结点的左右子树已经是堆。那么这棵树中哪个结点的左右子树是堆呢，很自然的发现是最后一个非叶子结点，所以我们在这里需要自下而上的调整这个完全二叉树。

（2）代码：

static void creatHeap(int[] a){  
            //自下而上调整堆  
            for(int i=(a.length - 1) / 2; i >= 0; i--)  
                maxHeap(a, i);  
            System.out.println("建堆:"+Arrays.toString(a));   
        }

（3）示例

待排序序列：![0_1315787970NpMp.gif][] A\[6\]=\{3,5,8,9,1,2\},

以8为根结点调整堆后：因为8>2，此处不进行记录移动操作

以5为根结点调整堆后：5<9,5跟9互换

![0_1315788650L0Jq.gif][] A\[6\]=\{3,9,8,5,1,2\}

以3为根结点调整堆后：3<9,3跟9互换

![0_13157887860lLm.gif][] A\[6\]=\{ 9,3,8,5,1,2\}

以9为根的左子树不满足大顶堆的性质，所以以3为跟调整堆,即交换3和5，得A\[6\]=\{9,5,8,3,1,2\}

（4）时间代价分析

从最后一个非叶子结点到第二个结点，总共循环了n/2-1次，每次调用maxHeap函数，4.3中已经分析过maxHeap时间复杂度为O（log**2**n）。所以建堆的时间复杂度为O（n\*log**2**n）

**d.堆排序**

（1）堆排序过程

也许有的朋友想问：不是讲堆排序吗，为什么不直接讲呢，而是先叙述筛选法和建堆呢？因为筛选法和建堆就构成了堆排序，讲到这里，堆排序可以说是水到渠成。所以一定要理解筛选法和建堆的过程。

过程描述：1、建堆 2、将堆顶记录和堆中最后一个记录交换 3、筛选法调整堆，堆中记录个数减少一个，重复第2步。整个过程中堆是在不断的缩减。

（2）代码

public static  void sort(int[] a){   
            System.out.println("开始排序:"+Arrays.toString(a));   
            int arrayLength=a.length;   
            //建堆    
            creatHeap(a);
    
            //循环调整堆
            for(int i = arrayLength-1;i > 0 ;i--){   
                //交换堆顶和最后一个元素   
                swap(a, 0, i);   
                System.out.println("交换:"+Arrays.toString(a));   
    
                maxHeap(a, 0);   
                System.out.println("调整堆:"+Arrays.toString(a));   
    
            }   
        }

（3）示例  
0.待排序序列：

![0_1315787970NpMp.gif][] A\[6\]=\{3,5,8,9,1,2\},

1.建堆后（建堆过程参见4.4）：

![0_1315790133I1zi.gif][] A\[6\]=\{9,3,8,5,1,2\}

2.9和2交换，然后把9从堆中去掉后：

![0_1315790215m09l.gif][] A\[6\]=\{ 2,3,8,5,1,9\}

3.筛选法调整堆A\[5\]=\{2,3,8,5,1\}后（调整过程参见4.3）：

![0_1315790555WJYs.gif][] A\[6\]=\{8,3,2,5,1,9\}

4.堆顶记录与最后一个记录互换，重复第二步，但是堆顶记录和最后一个记录的值变了

（4）堆排序性能分析

此外堆排序是不稳定的原地排序算法。

**3)时间复杂度：**

O（n\*log**2** n）

堆排序时间=建堆时间+调整堆时间。从上文中知道建堆时间复杂度为O（n\*log**2**n）。筛选法调整堆（maxHeap函数）时间O（log**2**n），总共循环了n-1次maxHeap函数，所以调整堆时间复杂度为O（n\*log**2**n）。得出堆排序时间复杂度O（n\*log**2**n）。

熟悉了堆排序的过程后，可以发现堆排序不存在最佳情况，待排序序列是有序或者逆序时，并不对应于堆排序的最佳或最坏情况。且在最坏情况下时间复杂度也是O（n\*log**2** n）。

**4)空间复杂度：** O(1)

**5)是否稳定：不稳定**

**6)源码：**

package com.apple.sort;
 
 import java.util.Arrays;
 
 /**
 * 选择排序 
 * 堆排序 
 * @date 2016年8月1日
 * @author tianjinsong
 */
 public class HeapSort {
 
 public static void main(String[] args) {
 int a[] ={4,5,3,9,1,6}; 
 HeapSort.sort(a);
 }
 
 public static void sort(int[] a){ 
 System.out.println("开始排序:"+Arrays.toString(a)); 
 int arrayLength=a.length; 
 //建堆 
 creatHeap(a);
 
 //循环调整堆
 for(int i = arrayLength-1;i > 0 ;i--){ 
 //交换堆顶和最后一个元素 
 swap(a, 0, i); 
 System.out.println("交换:"+Arrays.toString(a)); 
 maxHeap(a, 0); 
 System.out.println("调整堆:"+Arrays.toString(a)); 
 } 
 } 
 
 static void creatHeap(int[] a){ 
 //自下而上调整堆 
 for(int i=(a.length - 1) / 2; i >= 0; i--) 
 maxHeap(a, i); 
 System.out.println("建堆:"+Arrays.toString(a)); 
 } 
 
 private static void swap(int[] data, int i, int j) { 
 int tmp=data[i]; 
 data[i]=data[j]; 
 data[j]=tmp; 
 } 
 
 //堆调整，使其生成最大堆 
 private static void maxHeap(int[] data, int parentIndex) { 
 int lastIndex = data.length -1;
 int left,right,largest; 
 largest=left=2 * parentIndex + 1; 
 
 // 如果左子节点大于父节点，则将左子节点作为最大节点 
 if (left > lastIndex) { 
 return;
 } 
 right = left + 1;
 // 如果右子节点比最大节点还大，那么最大节点应该是右子节点 
 if(right<=lastIndex && data[right] > data[left]){ 
 largest=right; 
 } 
 
 if(data[largest] > data[parentIndex] ){//根结点的值不是最大时,交换a[i]，a[largest] 
 swap(data, largest, parentIndex);
 //自上而下调整堆 
 maxHeap(data, largest); 
 } 
 } 
 
 }

## 冒泡排序 ##

**1)基本思想：**

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

**2)图解：**

![24171547-a3280c1d447746928e4c6fa395843940.png][]

**3)时间复杂度：**

最好O(n)------最坏O(n2)-------平均O(n2)

•若文件初状为正序，则一趟起泡就可完成排序，排序码的比较次数为n-1，且没有记录移动，时间复杂度是O(n)

•若文件初态为逆序，则需要n-1趟起泡，每趟进行n-i次排序码的比较，且每次比较都移动三次，比较和移动次数均达到最大值∶O(n2)

•起泡排序平均时间复杂度为O(n2)

**4)空间复杂度：** O(1)

**5)是否稳定：不稳定**

**6)源码：**

package com.apple.sort;
 /**
 * 交换排序
 * 冒泡排序
 * @date 2016年8月2日
 */
 public class BubbleSort {
 
 public static void main(String[] args) {
 int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
 System.out.println("排序之前：");
 for (int i = 0; i < a.length; i++) {
 System.out.print(a[i]+" ");
 }
 //冒泡排序
 BubbleSort2(a, a.length);
 
 System.out.println();
 System.out.println("排序之后：");
 for (int i = 0; i < a.length; i++) {
 System.out.print(a[i]+" ");
 }
 }
 
 //基础版
 public static void BubbleSort1(int[] a, int n){
 for (int i = 0; i < n; i++) {
 for(int j = 0; j < n - i - 1; j++){
 //这里-i主要是每遍历一次都把最大的i个数沉到最底下去了，没有必要再替换了
 if(a[j] > a[j+1]){
 int temp = a[j];
 a[j] = a[j+1];
 a[j+1] = temp;
 }
 }
 }
 }
 
 //改进版
 public static void BubbleSort2(int a[], int n) {
 int j, k;
 int flag;
 int temp;
 flag = n;
 while (flag > 0){
 k = flag;
 flag = 0;
 for (j = 1; j < k; j++){
 if (a[j - 1] > a[j]){
 temp = a[j - 1];
 a[j - 1] = a[j];
 a[j] = temp;
 flag = j;
 }
 }
 }
 }
 }

## 快速排序 ##

**1)基本思想：**

选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

**2)图解：**

以一个数组作为示例，取区间第一个数为基准数。

初始时，i = 0; j = 9; X = a\[i\] = 72

由于已经将a\[0\]中的数保存到X中，可以理解成在数组a\[0\]上挖了个坑，可以将其它数据填充到这来。

从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a\[8\]挖出再填到上一个坑a\[0\]中。a\[0\]=a\[8\]; i++; 这样一个坑a\[0\]就被搞定了，但又形成了一个新坑a\[8\]，这怎么办了？简单，再找数字来填a\[8\]这个坑。这次从i开始向后找一个大于X的数，当i=3，符合条件，将a\[3\]挖出再填到上一个坑中a\[8\]=a\[3\]; j--;

数组变为：

i = 3; j = 7; X=72

再重复上面的步骤，**先从后向前找，再从前向后找**。

从j开始向前找，当j=5，符合条件，将a\[5\]挖出填到上一个坑中，a\[3\] = a\[5\]; i++;

从i开始向后找，当i=5时，由于i==j退出。

此时，i = j = 5，而a\[5\]刚好又是上次挖的坑，因此将X填入a\[5\]。

数组变为：

可以**看出a\[5\]前面的数字都小于它，a\[5\]后面的数字都大于它**。因此再对a\[0…4\]和a\[6…9\]这二个子区间**重复**上述步骤就可以了。

对挖坑填数进行总结

1．i =L; j = R; 将基准数挖出形成第一个坑a\[i\]。

2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a\[i\]中。

3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a\[j\]中。

4．再重复执行2，3二步，直到i==j，将基准数填入a\[i\]中。

**3)时间复杂度：**

最好O(nlgn)\------最坏O(n2)-------平均O(n2)

最坏时间复杂度：最坏情况是每次划分选取的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果是基准左边的子区间为空（或右边的子区间为空），而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。因此，快速排序必须做 n-1 次划分，第 i 次划分开始时区间长度为 n-i-1, 所需的比较次数为 n-i(1<=i<=n-1), 故总的比较次数达到最大值 Cmax =n(n-1)/2=O(n^2) 。如果按上面给出的划分[算法][Link 4]，每次取当前无序区的第 1 个记录为基准，那么当文件的记录已按递增序（或递减序）排列时，每次划分所取的基准就是当前无序区中关键字最小（或最大）的记录，则快速排序所需的比较次数反而最多。

最好时间复杂度：在最好情况下，每次划分所取的基准都是当前无序区的“中值”记录，划分的结果与基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数为 O(n×lgn)。

用递归树来分析最好情况下的比较次数更简单。因为每次划分后左、右子区间长度大致相等，故递归树的高度为 O(lgn), 而递归树每一层上各结点所对应的划分过程中所需要的关键字比较次数总和不超过 n，故整个排序过程所需要的关键字比较总次数C(n)=O(n×lgn) 。因为快速排序的记录移动次数不大于比较的次数，所以快速排序的最坏时间复杂度应为 O(n^2 )，最好时间复杂度为 O(n×lgn)。

**4)空间复杂度：** O(lgn)-O(n)

快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为 O(lgn), 故递归后所需栈空间为 O(lgn) 。最坏情况下，递归树的高度为 O(n), 所需的栈空间为 O(n) 。

**5)是否稳定：不稳定**

**6)源码：**

package com.apple.sort;
 /**
 * 交换排序：快速排序
 * @date 2016年8月2日
 */
 public class FastSort {
 
 public static void main(String[] args) {
 int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
 System.out.println("排序之前：");
 for (int i = 0; i < a.length; i++) {
 System.out.print(a[i]+" ");
 }
 //快速排序
 quickSort(a,0,a.length-1);
 
 System.out.println();
 System.out.println("排序之后：");
 for (int i = 0; i < a.length; i++) {
 System.out.print(a[i]+" ");
 }
 }
 
 
 private static void quickSort(int[] a, int left, int right) {
 if(left < right){ //如果不加这个判断递归会无法退出导致堆栈溢出异常
 int temp = a[left];//基准元素
 int low = left, high = right; 
 while(low<high){
 //找到比基准元素小的元素位置
 while(low<high && a[high]>=temp){
 high--;
 }
 a[low] = a[high]; 
 while(low<high && a[low]<=temp){
 low++;
 }
 a[high] = a[low];
 }
 a[low] = temp;
 quickSort(a, left, low -1);
 quickSort(a, low +1, right);
 }
 }
 
 }

## 归并排序 ##

**1)基本思想：**

将待排序序列R\[0...n-1\]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。

综上可知：归并排序其实要做两件事：

（1）“分解”——将序列每次**折半划分**。

（2）“合并”——将划分后的序列段**两两合并后排序**。

**2)图解：**

我们先来考虑第二步，**如何合并**？

在每次合并过程中，都是对两个有序的序列段进行合并，然后排序。

这两个有序序列段分别为 R\[low, mid\] 和 R\[mid+1, high\]。

先将他们合并到一个局部的**暂存数组**R2中，带合并完成后再将R2复制回R中。

为了方便描述，我们称 R\[low, mid\] 第一段，R\[mid+1, high\] 为第二段。

每次从两个段中取出一个记录进行关键字的比较，将较小者放入R2中。最后将各段中余下的部分直接复制到R2中。

经过这样的过程，R2已经是一个有序的序列，再将其复制回R中，一次合并排序就完成了。

**核心代码**

private static void merge(int[] a, int left, int middle, int right) {
 int[] tmpArr = new int[a.length];
 int mid = middle+1; //右边的起始位置
 int tmp = left;
 int third = left;
 while(left<=middle && mid<=right){
 //从两个数组中选取较小的数放入中间数组
 if(a[left]<=a[mid]){
 tmpArr[third++] = a[left++];
 }else{
 tmpArr[third++] = a[mid++];
 }
 }
 //将剩余的部分放入中间数组
 while(left<=middle){
 tmpArr[third++] = a[left++];
 }
 while(mid<=right){
 tmpArr[third++] = a[mid++];
 }
 //将中间数组复制回原数组
 while(tmp<=right){
 a[tmp] = tmpArr[tmp++];
 }
 }

掌握了合并的方法，接下来，让我们来了解 **如何分解**。

[![318837-20160422105330898-383478645.png][]][318837-20160422105330898-383478645.png]

在某趟归并中，设各子表的长度为**gap**，则归并前R\[0...n-1\]中共有**n/gap**个有序的子表：R\[0...gap-1\], R\[gap...2\*gap-1\], ... , R\[(n/gap)\*gap ... n-1\]。

调用Merge**将相邻的子表归并**时，必须对表的特殊情况进行特殊处理。

若子表个数为奇数，则最后一个子表无须和其他子表归并（即本趟处理轮空）：若子表个数为偶数，则要注意到最后一对子表中后一个子表区间的上限为n-1。

**核心代码**

private static void mergeSort(int[] a, int left, int right) {
 if(left<right){
 int middle = (left+right)/2;
 //对左边进行递归
 mergeSort(a, left, middle);
 //对右边进行递归
 mergeSort(a, middle+1, right);
 //合并
 merge(a,left,middle,right);
 }
 }

**3)时间复杂度：**

O(n\*log2n)

归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它的时间复杂度是 O(n\*log2n) 。

**4)空间复杂度：**  O(n)

归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间：n + logn；所以空间复杂度为: O(n)

**5)是否稳定：稳定**

**6)延伸：**

归并排序算法改进和优化？

1.利用插入排序优化归并排序

2.不回写+非递归优化归并排序

3.利用自然合并排序优化归并排序

4.双向自然合并排序优化归并排序算法

5.Strand Sort算法

**7)源码：**

package com.apple.sort;
 /**
 * 归并排序
 * @date 2016年8月2日
 */
 public class MergeSort {
 public static void main(String[] args) {
 int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
 System.out.println("排序之前：");
 for (int i = 0; i < a.length; i++) {
 System.out.print(a[i]+" ");
 }
 //归并排序
 mergeSort(a,0,a.length-1);
 System.out.println();
 System.out.println("排序之后：");
 for (int i = 0; i < a.length; i++) {
 System.out.print(a[i]+" ");
 }
 }
 
 private static void mergeSort(int[] a, int left, int right) {
 if(left<right){
 int middle = (left+right)/2;
 //对左边进行递归
 mergeSort(a, left, middle);
 //对右边进行递归
 mergeSort(a, middle+1, right);
 //合并
 merge(a,left,middle,right);
 }
 }
 
 private static void merge(int[] a, int left, int middle, int right) {
 int[] tmpArr = new int[a.length];
 int mid = middle+1; //右边的起始位置
 int tmp = left;
 int third = left;
 while(left<=middle && mid<=right){
 //从两个数组中选取较小的数放入中间数组
 if(a[left]<=a[mid]){
 tmpArr[third++] = a[left++];
 }else{
 tmpArr[third++] = a[mid++];
 }
 }
 //将剩余的部分放入中间数组
 while(left<=middle){
 tmpArr[third++] = a[left++];
 }
 while(mid<=right){
 tmpArr[third++] = a[mid++];
 }
 //将中间数组复制回原数组
 while(tmp<=right){
 a[tmp] = tmpArr[tmp++];
 }
 }
 }

## 基数排序 ##

**1)基本思想：**

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

**2)图解：**

基数排序是通过“分配”和“收集”过程来实现排序。而这个思想该如何理解呢？请看以下例子。

（1）假设有欲排数据序列如下所示：

73 22 93 43 55 14 28 65 39 81

首先根据个位数的数值，在遍历数据时将它们各自分配到编号0至9的桶（个位数值与桶号一一对应）中。

分配结果（逻辑想象）如下图所示：

![21184846-adf7d6848b5b4378b396746e9af24ccb.png][]

分配结束后。接下来将所有桶中所盛数据按照桶号由小到大（桶中由顶至底）依次重新收集串起来，得到如下仍然无序的数据序列：

81 22 73 93 43 14 55 65 28 39

接着，再进行一次分配，这次根据十位数值来分配（原理同上），分配结果（逻辑想象）如下图所示：

![21184914-ac11c70e387249e89e5ef16aa0ce4566.png][]

分配结束后。接下来再将所有桶中所盛的数据（原理同上）依次重新收集串接起来，得到如下的数据序列：

14 22 28 39 43 55 65 73 81 93

观察可以看到，此时原无序数据序列已经排序完毕。如果排序的数据序列有三位数以上的数据，则重复进行以上的动作直至最高位数为止。

基于两种不同的排序顺序，我们将基数排序分为LSD（Least significant digital）或MSD（Most significant digital），

LSD的排序方式由数值的最右边（低位）开始，而MSD则相反，由数值的最左边（高位）开始。

注意一点：LSD的基数排序适用于位数少的数列，如果位数多的话，使用MSD的效率会比较好。

MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。

在进行完最低位数的分配后再合并回单一的数组中。

**3)时间复杂度：**

最好[O(d(n+r))][O_d_n_r]\------最坏[O(d(n+r))][O_d_n_r]\-------平均[O(d(n+r))][O_d_n_r][d为位数r为基数][O_d_n_r]

**4)空间复杂度：** [O(n+r)][O_d_n_r]

**5)是否稳定：稳定**

**6)源码：**

package com.apple.sort;
 
 /**
 * 基数排序 
 */
 public class RadixSort {
 
 public static void main(String[] args) {
 int[] data = { 73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 10 };
 
 System.out.println(radixSortAsc(data));
 for (int i = 0; i < data.length; i++) {
 System.out.print(data[i] + " ");
 }
 }
 
 public static int[] radixSortAsc(int[] arr) {
 // 从低位往高位循环
 for (int d = 1; d <= getMax(arr); d++) {
 // 临时数组，用来存放排序过程中的数据
 int[] tmpArray = new int[arr.length];
 // 位记数器，从第0个元素到第9个元素依次用来记录当前比较位是0的有多少个...是9的有多少个数
 int[] count = new int[10];
 // 开始统计0有多少个，并存储在第0位，再统计1有多少个，并存储在第1位..依次统计到9有多少个
 // { 73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 10 };
 for (int i = 0; i < arr.length; i++) {
 count[digit(arr[i], d)] += 1;// 统计该位上有多少个数字 比如第一位上0有多少个
 }
 /*
 * 比如某次经过上面统计后结果为：[0, 2, 3, 3, 0, 0, 0, 0, 0, 0]则经过下面计算后 结果为： [0, 2,
 * 5, 8, 8, 8, 8, 8, 8, 8]但实质上只有如下[0, 2, 5, 8, 0, 0, 0, 0, 0, 0]中
 * 非零数才用到，因为其他位不存在，它们分别表示如下：2表示比较位为1的元素可以存放在索引为1、0的
 * 位置，5表示比较位为2的元素可以存放在4、3、2三个(5-2=3)位置，8表示比较位为3的元素可以存放在
 * 7、6、5三个(8-5=3)位置
 */
 for (int i = 1; i < 10; i++) {
 count[i] += count[i - 1];
 }
 
 /*
 * 注，这里只能从数组后往前循环，因为排序时还需保持以前的已排序好的 顺序，不应该打
 * 乱原来已排好的序，如果从前往后处理，则会把原来在前面会摆到后面去，因为在处理某个
 * 元素的位置时，位记数器是从大到到小（count[digit(arr[i], d)]--）的方式来处
 * 理的，即先存放索引大的元素，再存放索引小的元素，所以需从最后一个元素开始处理。
 * 如有这样的一个序列[212,213,312]，如果按照从第一个元素开始循环的话，经过第一轮
 * 后（个位）排序后，得到这样一个序列[312,212,213]，第一次好像没什么问题，但问题会
 * 从第二轮开始出现，第二轮排序后，会得到[213,212,312]，这样个位为3的元素本应该
 * 放在最后，但经过第二轮后却排在了前面了，所以出现了问题
 */
 for (int i = arr.length - 1; i >= 0; i--) {// 只能从最后一个元素往前处理
 // for (int i = 0; i < arr.length; i++) {//不能从第一个元素开始循环
 tmpArray[count[digit(arr[i], d)] - 1] = arr[i];
 count[digit(arr[i], d)]--;
 }
 //System.arraycopy(tmpArray, 0, arr, 0, tmpArray.length);
 for(int i=0;i<arr.length;i++){
 arr[i]=tmpArray[i];
 }
 }
 return arr;
 }
 //求出最大数的位数的函数
 public static int getMax(int[] array) {
 // 取出最大数然后求出最大的位数
 int max = array[0];
 for (int j = 1; j < array.length; j++) {
 if (array[j] > max) {
 max = array[j];
 }
 }
 int time = 0;
 // 判断位数;
 while (max > 0) {
 max /= 10;
 time++;
 }
 return time;
 // return String.valueOf(max).length();也可以根据字符串长度返回
 }
 
 /**
 * 取数xxx上的第d位数字
 * 
 * @param x
 * 数字
 * @param d
 * 第几位，从低位到高位
 * @return
 */
 public static int digit(int num, int d) {
 int pow = 1;
 while (--d > 0) {
 pow *= 10;
 }
 return num / pow % 10;
 }
 
 }

# 时间、空间复杂度 #

<table style="width:587px; height:1px"> 
 <tbody> 
 <tr> 
 <td> 排序法 </td> 
 <td>最差时间分析</td> 
 <td>平均时间复杂度</td> 
 <td>稳定度</td> 
 <td>空间复杂度</td> 
 </tr> 
 <tr> 
 <td align="center">冒泡排序</td> 
 <td align="center">O(n2)</td> 
 <td align="center">O(n2)</td> 
 <td align="center">稳定</td> 
 <td align="center">O(1)</td> 
 </tr> 
 <tr> 
 <td align="center">快速排序</td> 
 <td align="center">O(n2)</td> 
 <td align="center">O(n*log2n)</td> 
 <td align="center">不稳定</td> 
 <td align="center">O(log2n)~O(n)</td> 
 </tr> 
 <tr> 
 <td align="center">选择排序</td> 
 <td align="center">O(n2)</td> 
 <td align="center">O(n2)</td> 
 <td align="center">稳定</td> 
 <td align="center">O(1)</td> 
 </tr> 
 <tr> 
 <td align="center">二叉树排序</td> 
 <td align="center">O(n2)</td> 
 <td align="center">O(n*log2n)</td> 
 <td align="center">不一顶</td> 
 <td align="center">O(n)</td> 
 </tr> 
 <tr> 
 <td align="center"> 插入排序 </td> 
 <td align="center">O(n2)</td> 
 <td align="center">O(n2)</td> 
 <td align="center">稳定</td> 
 <td align="center">O(1)</td> 
 </tr> 
 <tr> 
 <td align="center">堆排序</td> 
 <td align="center">O(n*log2n)</td> 
 <td align="center">O(n*log2n)</td> 
 <td align="center">不稳定</td> 
 <td align="center">O(1)</td> 
 </tr> 
 <tr> 
 <td align="center">希尔排序</td> 
 <td align="center">O</td> 
 <td align="center">O</td> 
 <td align="center">不稳定</td> 
 <td align="center">O(1)</td> 
 </tr> 
 </tbody> 
</table>

# 问题解析 #

## 为何排序的稳定性很重要？ ##

在初学排序时会觉得稳定性有这么重要吗？两个一样的元素的顺序有这么重要吗？其实很重要。在基数排序中显得尤为突出，如下：

![1357739159_8849.GIF][]

**算法导论习题8.3-2**说：如果对于不稳定的算法进行改进，使得那些不稳定的算法也稳定？

其实很简单，只需要在每个输入元素加一个index，表示初始时的数组索引，当不稳定的算法排好序后，对于相同的元素对index排序即可。

基于比较的排序都是遵循“决策树模型”，而在决策树模型中，我们能证明给予比较的排序算法最坏情况下的运行时间为Ω(nlgn)，证明的思路是因为将n个序列构成的决策树的叶子节点个数至少有n!，因此高度至少为nlgn。

线性时间排序虽然能够理想情况下能在线性时间排序，但是每个排序都需要对输入数组做一些假设，比如计数排序需要输入数组数字范围为\[0,k\]等。

在排序算法的正确性证明中介绍了”循环不变式“，他类似于数学归纳法，"初始"对应"n=1"，"保持"对应"假设n=k成立，当n=k+1时"。

##    用递归排序和循环排序有什么不同？ ##

# 参与文献 #

内容大部分来源于网络，感谢原作者的分享！

http://www.cnblogs.com/liuling/p/2013-7-24-01.html

http://blog.csdn[.NET][]/wuxinyicomeon/article/details/5996675

http://blog.csdn[.NET][]/morewindows/article/details/6665714

http://blog.csdn.net/xiazdong

http://www.cnblogs.com/heyuquan/p/insert-sort.html

[http://blog.csdn.net/morewindows/article/details/6684558][http_blog.csdn.net_morewindows_article_details_6684558]

http://blog.chinaunix[.NET][]/uid-26404477-id-3331118.html

[http://chenzehe.iteye.com/blog/481188][http_chenzehe.iteye.com_blog_481188]

[24160822-d0957aa2ca8a4500bfc84dbf36865578.png]: /images/20220715/d69a883eb9614eac9ca832628d728189.png
[n_n-1_2]: http://zhidao.baidu.com/link?url=D1uGyXzk3biP8YR-tKHq1_YHgZZmojMd0XzWlPxSWoYdhaTZdlRyd-FXaVqGNaYpgVHe0Lh3mMKPCwNH2E5C6q
[24162933-28ad5af710d8441d97ee22fddb873a84.jpg]: /images/20220715/3a822724f5b448dbb50da05560a7b79f.png
[24164131-db4877dab9c94b63bcfb2cdf7f9cbf69.png]: /images/20220715/1ea5ef33e0824437ac13518048db5426.png
[nlogn]: http://blog.csdn.net/bluetjs/article/details/52401246
[Link 1]: http://baike.baidu.com/view/19016.htm
[Link 2]: http://baike.baidu.com/view/2586460.htm
[24170221-5e84d6b12ea545618b673783789b5803.png]: /images/20220715/ea1544fcf39047f5a4197846fea6f6d2.png
[Link 3]: http://lib.csdn.net/base/31
[0_1315782402S22O.gif]: /images/20220715/671f145f807143b5b410df11b012b7f0.png
[0_1315782894Vxz8.gif]: /images/20220715/e769e8c474184116a970be953a0e4c5d.png
[0_1315784489Yw4n.gif]: /images/20220715/93c0ec501c7641fdacaea0a6a1ee7f90.png
[0_1315784510fuuq.gif]: /images/20220715/88653155e6414d01b6458ec12ef8fc1f.png
[0_1315787970NpMp.gif]: /images/20220715/28120ef1066b4dd98322a9c38c44889c.png
[0_1315788650L0Jq.gif]: /images/20220715/c3742d1a465c451c89a6c318aae9e40d.png
[0_13157887860lLm.gif]: /images/20220715/4229986e5ee9438b818ef3f1662f9282.png
[0_1315790133I1zi.gif]: /images/20220715/513a1975b9974376b7edfd5d9ea57029.png
[0_1315790215m09l.gif]: /images/20220715/49f2298d7c884d7b89cf1f11ffba9a35.png
[0_1315790555WJYs.gif]: /images/20220715/c77f539cbc9646fdb91e5fb51b30319d.png
[24171547-a3280c1d447746928e4c6fa395843940.png]: /images/20220715/653e877561a14d84aaa35c26a088eeda.png
[Link 4]: http://lib.csdn.net/base/datastructure
[318837-20160422105330898-383478645.png]: /images/20220715/d562742b76714df092bb6b4cbfcc7844.png
[21184846-adf7d6848b5b4378b396746e9af24ccb.png]: /images/20220715/272621d2f89342f9bf1a694a86073b3a.png
[21184914-ac11c70e387249e89e5ef16aa0ce4566.png]: /images/20220715/6463968b86454132b46e46bf4bc607cc.png
[O_d_n_r]: http://blog.csdn.net/bluetjs/article/details/52402370
[1357739159_8849.GIF]: https://img-my.csdn.net/uploads/201301/09/1357739159_8849.GIF
[.NET]: http://lib.csdn.net/base/dotnet
[http_blog.csdn.net_morewindows_article_details_6684558]: http://blog.csdn.net/morewindows/article/details/6684558
[http_chenzehe.iteye.com_blog_481188]: http://chenzehe.iteye.com/blog/481188