[内排序]八大经典排序合集

青旅半醒 2023-10-06 09:34 34阅读 0赞

## 1 排序的基本概念 ##

假定排序的数据是由一组元素组成的表，而元素由若干个数据项组成，其中有一项可用来标识该元素，称为关键字项，其值称为关键字。关键字可用作排序运算的依据。

### 　 1.1 什么是排序 ###

所谓排序，就是整理表中的元素，使之按关键字递增或递减的顺序排列。

### 　 1.2 排序的稳定性 ###

当待排序元素的关键字各不相同时，排序的结果是唯一的，否则排序的结果不一定唯一。

如果待排序的表中，存在多关键字相同的元素，经过排序后这些具有相同关键字的元素之间的相对次序保持不变，则称这种排序方法是**稳定的**；反之，若具有相同关键字的元素之间的相对次序发生变化，则称这种排序方法是**不稳定的**。

注意，排序算法的稳定性是针对所有输入实例而言的。也就是说，在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。

### 　 1.3 内排序和外排序 ###

在排序过程中，若整个表都是放在内存中处理，排序时不涉及内、外存数据的交换，则称之为**内排序**；反之，若排序过程中要进行内。外存数据的交换，则称之为**外排序**。

内排序适用于元素个数不是很多的小表，外排序则适用于元素个数很多，不能一次将全部元素放入内存的大表。

按所用的策略不同，排序方法还可以分为需要关键字比较和不需要关键字比较两类。需要关键字比较的排序方法有插入排序。选择排序。交换排序和归并排序；不需要关键字比较的排序方法有基数排序。

![format_png][]

图1.1 排序的分类

## 2 插入排序 ##

插入排序基本思想：每次将一个待排序的元素，按其关键字大小插入到已经排好序的子表中的适当位置，直到全部元素插入完成为止。

### 　 2.1 直接插入排序 ###

#### 　　1. 排序思路 ####

假设待排序的元素存放在数组 Data\[0..n-1\] 中，排序过程中的某一时刻，Data 被划分成两个子区间 Data\[0..i-1\] 和 Data\[i..n-1\]（刚开始时 i=1，有序区只有 Data\[0\] 一个元素），其中，前一个子区间是已排好序的**有序区**，后一个子区间则是当前未排序的部分，称其为**无序区**。直接插入排序的一趟操作是将当前无序区的开头元素 Data\[i\] （1 <= i <= n-1）插入到有序区 Data\[0..i-1\] 中适当的位置上，使 Data\[0..i\] 变为新的有序区，如图2.1所示。这种方法通常称为增量法，因为它每趟操作使有序区增加一个元素。

![format_png 1][]

说明：直接插入排序每趟产生的有序区并一定是全局有序区，也就是说有序区中的元素并不一定放在其最终的位置上。当一个元素在整个排序结束前就已经放在其最终的位置上，称为归位。

#### 　 2. 直接插入排序实例 ####

设待排序的表有 10 个元素，其关键字为 \{9,8,7,6,5,4,3,2,1,0\}。以下为直接插入排序的排序过程：

![format_png 2][]

图中用方括号表示每趟操作后的有序区。每趟向有序区中插入一个元素（用方框表示），并保持有序区中的元素仍有序。

#### 　　3. 排序算法 ####

1 public class InsertSort {
     2     public static void insertSort(int[] Data) {
     3         int temp , j;
     4         for(int i = 0; i < Data.length; i++) {
     5             temp = Data[i];
     6             j = i-1;                        //从右向左在有序区Data[0..i-1]中找Data[i]的插入位置
     7             while(j >= 0 && temp < Data[j]) {
     8                 Data[j+1] = Data[j];        //将大于Data[i]的元素后移
     9                 j--;
    10             }
    11             Data[j+1] = temp;                //在j+1处插入Data[i]
    12         }
    13     }
    14     
    15     public static void main(String[] args) {
    16         int[] Data = {9,8,7,6,5,4,3,2,1,0};
    17         
    18         insertSort(Data);
    19         
    20         System.out.println("直接插入排序的结果：");
    21         for(int i = 0; i < Data.length; i++) {
    22             System.out.print(Data[i]+" ");
    23         }
    24     }
    25 }

#### 　 4. 算法分析 ####

时间复杂度：O(n2)；

空间复杂度：O(1)；

稳定性：稳定；

复杂性：简单。

#### 　 5. 折半插入排序 / 二分插入排序 ####

##### 　　5.1 排序思路 #####

直接插入排序将无序区中开头元素 Data\[i\]（1 <= i <= n-1）插入到有序区 Data\[0..i-1\]中，此时可以采用折半查找方法先在 Data\[0..i-1\] 中找到插入的位置，再通过移动元素进行插入。

在Data\[low..high\]（初始时 low=0，high=i-1）中采用折半查找插入 Data\[i\] 的位置为 Data\[high+1\]，再将 Data\[high+1..i-1\] 中的元素后移一个位置，并置 Data\[high+1\] = Data\[i\]。

说明：和直接插入排序一样，折半插入排序每趟产生的有序区并不一定是全局有序区。

##### 　　5.2 排序算法 #####

1 public class HalfInsertSort {
     2     public static void halfInsertSort(int[] Data) {
     3         int low , high , mid;
     4         int temp;
     5         for(int i = 1; i < Data.length; i++) {
     6             temp = Data[i];                //将Data[i]保存在temp中
     7             low = 0;
     8             high = i-1;
     9             while( low <= high) {        //在Data[low..high]中折半查找有序插入的位置
    10                 mid = (low+high) / 2;    //取中间位置
    11                 if(temp < Data[mid]) {
    12                     high = high-1;        //插入点在左半区
    13                 }else {
    14                     low = mid + 1;        //插入点在右半区
    15                 }
    16             }
    17             for(int j = i-1; j >= high+1; j--) {
    18                 Data[j+1] = Data[j];    //元素后移
    19             }
    20             Data[high+1] = temp;        //插入在Data[high+1]位置
    21         }
    22     }
    23     
    24     public static void main(String[] args) {
    25         int[] Data = {9,8,7,6,5,4,3,2,1,0};
    26         
    27         halfInsertSort(Data);
    28         
    29         System.out.println("折半插入排序的结果：");
    30         for(int i = 0; i < Data.length; i++) {
    31             System.out.print(Data[i]+" ");
    32         }
    33     }
    34 }

#### 　 5.3 算法分析 ####

从上述算法中看到，当初始数据序列为正序时，关键字的比较次数并不能减少；当初始数据序列为反序时，关键字的比较次数也不会增加。

折半插入排序的元素移动次数与直接插入排序相同，不同的仅是变分散移动为集合移动。

就平均性能而言，折半查找优于顺序查找，所以折半插入排序优于直接插入排序。

时间复杂度为：O(n2)；

空间复杂度为：O(1)；

稳定性：稳定；

复杂性：简单。

### 　 2.2 希尔排序 ###

#### 　 1. 排序思路 ####

先取定一个小于数组长度 Data.length 的整数 gap（gap = Data.length / 2）作为第一个增量，把表的全部元素分成 gap 个组，所有相互之间距离为 gap 的倍数的元素放在同一个组中，在各组内进行直接插入排序；然后，减小增量 gap（gap = gap /2），重复上述的分组和排序过程，直至增量减小为 0，即所有元素放在同一组中进行直接插入排序。

说明：希尔排序每趟并不产生有序区，在最后一趟排序结束前，所有元素并不一定归位。但是每趟排序完成后，数据越来越接近有序。

#### 　 2. 希尔排序实例 ####

设待排序的表有 10 个元素，其关键字为 \{9,8,7,6,5,4,3,2,1,0\}。以下为直接插入排序的排序过程：

![format_png 3][]

第一趟排序时，d = 5 ，整个表被分成 5 组：（9,4），（8,3），（7,2），（6,1），（5,0），各组采用直接插入排序方法变成有序的，即结果分别为（4,9），（3,8），（2,7），（1,6）（0,5）。

第二趟排序时，d = 2，整个表分为两组：（4,2,0,8,6）和（3,1,9,7,5），各组采用直接插入排序方法变成有序的，即结果分别为（0,2,4,6,8）和（1,3,5,7,9）。

第三趟排序时，d = 1，整个表为一组，采用直接插入排序方法使整个数列有序，最终结果为（0,1,2,3,4,5,6,7,8,9）。

#### 　 3. 排序算法 ####

1 public class ShellSort {
     2     public static void shellSort(int[] Data) {
     3         int gap = Data.length / 2;                //增量置初值
     4         int temp = 0 , j = 0;
     5         while(gap > 0) {
     6             for(int i = gap; i < Data.length; i++) {    //对所有相隔gap位置的元素组采用直接插入排序
     7                 temp = Data[i];
     8                 j = i - gap;
     9                 while(j >= 0 && temp < Data[j]) {        //对相隔gap位置的元素组进行排序
    10                     Data[j+gap] = Data[j];
    11                     j -= gap;
    12                 }
    13                 Data[j+gap] = temp;
    14             }
    15             gap /= 2;                            //减小增量
    16         }
    17     }
    18     
    19     public static void main(String[] args) {
    20         int[] Data = {9,8,7,6,5,4,3,2,1,0};
    21         
    22         shellSort(Data);
    23         System.out.println("希尔排序的结果：");
    24         for(int i = 0; i < Data.length; i++) {
    25             System.out.print(Data[i]+" ");
    26         }
    27     }
    28 }

#### 　 4. 算法分析 ####

时间复杂度：O(n1.3)；

空间复杂度：O(1)；

稳定性：不稳定；

复杂性：较复杂。

## 3 交换排序 ##

### 　 3.1 冒泡排序 ###

#### 　 1. 排序思路 ####

通过无序区中相邻元素间关键字的比较和位置的交换，使关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”。整个算法是从最下面的元素开始，对每两个相邻的关键字进行比较，且使关键字较小的元素换至关键字较大的元素之上，使得经过一趟冒泡排序后，关键字最小的元素到达最上端。接着，再在剩下的元素中找关键字次小的元素，并把它交换到第二个位置上。依次类推，一直到所有元素都有序为止。

![format_png 4][]

说明：冒泡排序每趟产生的有序区一定是全局有序区，也就是说每趟产生的有序区中所有元素都归位了。

#### 　 2. 冒泡排序实例 ####

设待排序的表有 10 个元素，其关键字为 \{9,8,7,6,5,4,3,2,1,0\}。以下为冒泡排序的排序过程：

每次从无序区中冒出一个关键字最小的元素（用方框表示）并将其定位。

#### ![format_png 5][] ####

#### 　 3. 排序算法 ####

1 public class BubbleSort {
     2     public static void bubbleSort(int[] Data) {
     3         int temp = 0;
     4         for(int i = 0; i < Data.length-1; i++) {
     5             for(int j = Data.length-1 ; j > i; j--) {    //比较，找出本趟关键字最小的元素
     6                 if(Data[j] < Data[j-1]) {
     7                     temp = Data[j];                //Data[j-1]与Data[j]进行交换，将关键字最小的元素前移
     8                     Data[j] = Data[j-1];
     9                     Data[j-1] = temp;
    10                 }
    11             }
    12         }
    13     }
    14     
    15     public static void main(String[] args) {
    16         int[] Data = {9,8,7,6,5,4,3,2,1,0};
    17         
    18         bubbleSort(Data);
    19         System.out.println("冒泡排序的结果：");
    20         for(int i = 0; i < Data.length; i++) {
    21             System.out.print(Data[i]+" ");
    22         }
    23     }
    24 
    25 }

#### 　　4. 算法分析 ####

时间复杂度为：O(n2)；

空间复杂度为：O(1)；

稳定性：稳定；

复杂性：简单。

#### 　 5. 改进的冒泡排序算法 ####

在有些情况下，在第 i （i < n-1）趟时就已经排好序了，但算法仍执行后面几趟的比较。实际上，一旦算法中某一趟比较时没有出现任何元素交换，说明已排好序了，就可以结束本算法。为此，改进冒泡排序算法如下：

1 public class ImproveBubbleSort {    
     2     public static void improveBubbleSort(int[] Data) {
     3         boolean exchange;
     4         int temp = 0;
     5         for(int i = 0; i < Data.length-1; i++) {
     6             exchange = false;
     7             for(int j = Data.length-1; j > i; j--) {    //比较，找出本趟关键字最小的元素
     8                 if(Data[j] < Data[j-1]) {
     9                     temp = Data[j];                //Data[j-1]与Data[j]进行交换，将关键字最小的元素前移
    10                     Data[j] = Data[j-1];
    11                     Data[j-1] = temp;
    12                     exchange = true;
    13                 }
    14             }
    15             if(!exchange)                        //本趟没有发生交换，中途结束算法
    16                 return;
    17         }
    18     }
    19     
    20     public static void main(String[] args) {
    21         int[] Data = {9,8,7,6,5,4,3,2,1,0};
    22         
    23         improveBubbleSort(Data);
    24         System.out.println("改进冒泡排序的结果：");
    25         for(int i = 0; i < Data.length; i++) {
    26             System.out.print(Data[i]+" ");
    27         }
    28     }
    29 }

### 　 3.2 快速排序 ###

#### 　 1. 排序思路 ####

在待排序的 n 个元素中任取一个元素（通常取第一个元素）作为基准，把该元素放入适当的位置后，数据序列被此元素分成两部分，所有关键字比该元素关键字小的元素放置在前一部分，所有关键字比该元素关键字大的元素放置在后一部分，并把该元素排在这两部分的中间（称该元素归位），这个过程称做一趟快速排序，之后对所有划分出来的两部分分别重复上述过程，直至每部分内只有一个元素或为空为止。

![format_png 6][]

说明：快速排序每趟仅将一个元素归位。

#### 　 2. 快速排序实例 ####

设待排序的表有 10 个元素，其关键字为 \{6,8,7,9,0,1,3,2,4,5\}。以下为快速排序的排序过程：

其排序过程如图 3.4 所示（最后结果图（g）称为快速排序递归树）。第 1 趟是以 6 为基准将整个区间分为（5,4,2,3,0,1）和（9,7,8）两个子区间，并将 6 归位；对于每个子区间，又进行同样的排序，直到该子区间只有一个元素或不存在元素为止。

![format_png 7][]

#### 　 3. 排序算法 ####

1 public class QuickSort {
     2     public static void quickSort(int[] Data , int s , int t) {
     3         int i = s , j = t;                        //对Data[s]至Data[t]的元素进行快速排序
     4         int temp = 0;
     5         if(s < t) {                                //区间内至少存在两个元素的情况
     6             temp = Data[s];                        //用区间的第1个元素作为基准
     7             while(i != j) {                        //从区间两端交替向中间扫描，直至i = j为止
     8                 while(j > i && Data[j] >= temp)
     9                     j--;                        //从右向左扫描，找第1个小于temp的元素Data[j]
    10                 Data[i] = Data[j];                //找到这样的Data[j],Data[i]与Data[j]交换
    11                 while(i < j && Data[i] <= temp)
    12                     i++;                        //从左向右扫描，找第1个大于temp的元素Data[j]
    13                 Data[j] = Data[i];                //找到这样的Data[i],Data[i]与Data[j]交换
    14             }
    15             Data[i] = temp;
    16             quickSort(Data, s, i-1);            //对左区间递归排序
    17             quickSort(Data, i+1, t);            //对右区间递归排序
    18         }
    19     }
    20 
    21     public static void main(String[] args) {
    22         int[] Data = {6,8,7,9,0,1,3,2,4,5};
    23         
    24         quickSort(Data, 0, Data.length-1);
    25         System.out.println("快速排序的结果：");
    26         for(int i = 0; i < Data.length; i++) {
    27             System.out.print(Data[i]+" ");
    28         }
    29     }
    30 }

#### 　 4. 算法分析 ####

时间复杂度：O(nlog2n)；

空间复杂度：O(log2n)；

稳定性：不稳定；

复杂性：较复杂。

## 4 选择排序 ##

### 　 4.1 直接选择排序 ###

#### 　 1. 排序思路 ####

第 i 趟排序开始时，当前有序区和无序区分别为 Data\[0..i-1\] 和 Data\[i..n-1\]（0 <= i < n-1），该趟排序是从当前无序区中选出关键字最小的元素 Data\[k\]，将它与无序区的第 1 个元素 Data\[i\] 交换，使 Data\[0..i\] 和 Data\[i+1..n-1\] 分别变为新的有序区和新的无序区，如图4.1所示。因为每趟排序均使有序区中增加一个元素，且有序区中的元素关键字均不大于无序区中元素的关键字，即第 i 趟排序之后，Data\[0..i\] 中的关键字小于 Data\[i+1..n-1\] 中的所有关键字，所以进行 n-1 趟排序之后有 Data\[0..n-2\] 中的所有关键字小于等于 Data\[n-1\]，也就是说，经过 n-1 趟排序之后，整个表 Data\[0..n-1\] 递增有序。

![format_png 8][]　　说明：直接选择排序每趟产生的有序区一定是全局有序区，也就是说每趟产生的有序区中所有元素都归位了。

#### 2. 直接选择排序实例 ####

设待排序的表有 10 个元素，其关键字为 \{6,8,7,9,0,1,3,2,4,5\}。以下为直接选择排序的排序过程：

每趟选择出一个元素（带方框者）。

![format_png 9][]

#### 　 3. 排序算法 ####

1 public class SelectSort {
     2     public static void selectSort(int[] Data) {
     3         int k = 0;
     4         int temp = 0;
     5         for(int i = 0; i < Data.length-1; i++) {     //做第i趟排序
     6             k = i;
     7             for(int j = i+1; j < Data.length; j++) { //在当前无序区Data[i..n-1]中选最小的Data[k]
     8                 if(Data[j] < Data[k])
     9                     k = j;                             //k记下目前找到的最小关键字所在的位置
    10             }
    11             if(k != i) {                             //交换Data[i]和Data[k]
    12                 temp = Data[i];
    13                 Data[i] = Data[k];
    14                 Data[k] = temp;
    15             }
    16         }
    17     }
    18     
    19     public static void main(String[] args) {
    20         int[] Data = {6,8,7,9,0,1,3,2,4,5};
    21         
    22         selectSort(Data);
    23         System.out.println("直接选择排序的结果：");
    24         for(int i = 0; i < Data.length; i++) {
    25             System.out.print(Data[i]+" ");
    26         }
    27     }
    28 
    29 }

#### 4.算法分析 ####

时间复杂度：O(n2)；

空间复杂度：O(1)；

稳定性：不稳定；

复杂性：简单。

### 　 4.2 堆排序 ###

#### 1. 排序思路 ####

堆排序是一种树形选择排序方法，它的特点是，在排序过程中，将 Data\[0..n-1\] 看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字最大（或最小）的元素。

堆排序的排序过程中每次挑选最大元素归位，如图4.3所示。挑选最大元素的方法是将数组中存储的数据看成是一棵完全二叉树，利用完全二叉树中双亲节点和孩子节点之间的内在关系来选择关键字最大的元素。具体的做法是：把待排序的表的关键字存放在数组Data\[0..n-1\] 之中，将 Data 看做一棵二叉树，每个节点表示一个元素，源表的第一个元素Data\[0\] 作为二叉树的根，以下各元素 Data\[1..n-1\] 依次逐层从左到右顺序排列，构成一棵完全二叉树，节点 Data\[i\] 的左孩子是 Data\[2i+1\]，右孩子是 Data\[2i+2\]，双亲是 Data\[(i+1)/2-1\]。

![format_png 10][]

说明：堆排序每趟产生的有序区一定是全局有序区，也就是说每趟产生的有序区中所有元素都归位了。

#### 2. 直接选择排序实例 ####

设待排序的表有 10 个元素，其关键字为 \{6,8,7,9,0,1,3,2,4,5\}。以下为堆排序的排序过程：

其初始状态如图4.4（a）所示，通过第一个 for 循环调用 sift() 产生的初始堆如图4.4（b）所示，这时 Data 中关键字序列为\{9,8,7,6,5,1,3,2,4,0\}。

![format_png 11][]

堆排序的排序过程如图4.5所示，每输出一个元素，就对堆进行一次筛选调整。

![format_png 12][]

#### 　 3. 排序算法 ####

1 public class HeapSort {
     2     public static void heapSort(int[] Data , int n) {
     3         int temp = 0;
     4         for(int i = (n+1)/2-1; i >= 0; i--)    //循环建立初始堆，第一个双亲节点的位置序号为(n+1)/2-1
     5             sift(Data , i , n-1);
     6         for(int i = n-1; i >= 1; i--) {        //进行n-1趟堆排序，每一趟堆排序的元素个数减1
     7             temp= Data[0];                    //将最后一个元素同当前区间内Data[0]对换
     8             Data[0] = Data[i];
     9             Data[i] = temp;
    10             sift(Data , 0 , i-1);            //筛选Data[0]节点，得到i个节点的堆
    11         }
    12     }
    13     
    14     // 调整堆
    15     private static void sift(int[] Data, int low, int high) {
    16         int place = 2 * low + 1;            //该节点的左孩子在数组中的位置序号
    17         int temp = Data[low];                //保存当前节点
    18         while(place <= high) {
    19             if(place+1 <= high && Data[place] < Data[place+1])    //若右孩子较大，则把place指向右孩子
    20                 place++; 
    21             if(temp < Data[place]) {
    22                 Data[low] = Data[place];    //将Data[place]调整到双亲节点位置上
    23                 low = place;                //修改low和place值，以便继续向下筛选
    24                 place = 2 * low+1;
    25             } else
    26                 break;                        //筛选结束
    27         }
    28         Data[low] = temp;                    //被筛选节点的值放入最终位置
    29     }
    30     
    31     public static void main(String[] args) {
    32         int[] Data = {6,8,7,9,0,1,3,2,4,5};
    33         
    34         heapSort(Data,Data.length);
    35         System.out.println("堆排序的结果：");
    36         for(int i = 0; i < Data.length; i++) {
    37             System.out.print(Data[i]+" ");
    38         }
    39     }
    40 
    41 }

#### 4.算法分析 ####

时间复杂度：O(nlog2n)；

空间复杂度：O(1)；

稳定性：不稳定；

复杂性：较复杂。

## 5 归并排序 ##

#### 　 1. 排序思路 ####

归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并排是直接将两个有序的子表合并成一个有序的表即二路归并。

将 Data\[0..n-1\] 看成是 n 个长度为 1 的有序序列，然后进行亮亮归并，得到 \[n/2\] 个长度为 2（最后一个有序序列的长度可能为 1）的有序序列，再进行两两归并，得到 \[n/4\] 个长度为 4（最后一个有序序列的长度可能小于 4）的有序序列，…… ，直到得到一个长度为 n 的有序序列。

说明：归并排序每趟产生的有序区只是局部有序的，也就是说在最后一趟排序结束前，所有元素并不一定归位了。

#### 　 2. 归并排序实例 ####

设待排序的表有 10 个元素，其关键字为 \{18,2,20,34,12,32,6,16\}。以下为归并排序的排序过程：

采用二路归并排序时，需要进行 3 趟归并排序，其过程如图5.1所示。第 1 趟将每两个各含有一个元素的子表归并成一个新表，如将 \{18\} 和 \{2\} 排好序变为 \{2,18\}。第 2 趟将每两个各含有两个元素的子表归并成一个新表，如将 \{2,18\} 和 \{20,34\} 归并为\{2,18,20,34\}。第 3 趟将每两个各含有 4 个元素的子表归并成一个新表，产生最终有序表。

![format_png 13][]

#### 　 3. 排序算法 ####

1 public class MergeSort {
     2     /**
     3      * 自底向上的二路归并算法
     4      * @param Data
     5      */
     6     public static void mergeSort(int[] Data) {
     7         for(int i = 1; i < Data.length; i = 2*i) {    //进行log2n趟归并
     8             mergePass(Data , i , Data.length);
     9         }
    10     }
    11     /**
    12      * 对整个表进行一趟归并
    13      * @param Data
    14      * @param len    子表的长度
    15      * @param n        整个表的长度
    16      */
    17     private static void mergePass(int[] Data, int len, int n) {
    18         int  i = 0;
    19         for(i = 0; i + 2*len - 1 < n; i += 2*len) {        //归并len长的两个相邻子表
    20             merge(Data , i , i+len-1 , i+2*len-1);
    21         }
    22         if(i+len-1 < n) {                                //余下两个子表，后者长度小于len
    23             merge(Data , i , i+len-1 , n-1);            //归并这两个子表
    24         }
    25     }
    26     /**
    27      * 实现两个子表在同一个表中的一次归并
    28      * @param Data
    29      * @param low    第一个子表的开始
    30      * @param mid    第一个子表的结尾
    31      * @param high    第二个子表的结尾，第二个子表的开始为mid+1
    32      */
    33     private static void merge(int[] Data, int low, int mid, int high) {
    34         int[] num = new int[Data.length];    //暂存数组
    35         int i = low;    //第一个子表的开始下标
    36         int j = mid+1;    //第二个子表的开始下标
    37         int k = 0;        //暂存表的下标
    38         while( i <= mid && j <= high) {    //在第一个子表和第二个子表均为扫描完时循环
    39             if(Data[i] <= Data[j]) {    //将第一个子表中的元素放入暂存表num
    40                 num[k] = Data[i];
    41                 i++;
    42                 k++;
    43             } else {                    //将第二个子表中的元素放入暂存表num
    44                 num[k] = Data[j];
    45                 j++;
    46                 k++;
    47             }
    48         }
    49         while(i <= mid) {                //将第一个子表剩余部分复制到暂存表num
    50             num[k] = Data[i];
    51             i++;
    52             k++;
    53         }
    54         while(j <= high) {                //将第二个子表剩余部分复制到暂存表num
    55             num[k] = Data[j];
    56             j++;
    57             k++;
    58         }
    59         for(k = 0 , i = low; i <= high; k++ , i++) {    //将暂存表复制到源表中
    60             Data[i] = num[k];
    61         }
    62     }
    63     
    64     public static void main(String[] args) {
    65         int[] Data = {18,2,20,34,12,32,6,16};
    66         
    67         mergeSort(Data);
    68         System.out.println("归并排序的结果：");
    69         for(int i = 0; i < Data.length; i++) {
    70             System.out.print(Data[i]+" ");
    71         }
    72     }
    73 }

#### 　 4. 算法分析 ####

时间复杂度：O(nlog2n)；

空间复杂度：O(n)；

稳定性：稳定；

复杂性：较复杂。

## 6 基数排序 ##

#### 　 1. 排序思路 ####

基数排序有两种：最低位优先（LSD）和最高位优先（MSD）。最低位优先的过程是：先按最低位的值对元素进行排序，在此基础上，再按次低位进行排序，以此类推，由低位向高位，每趟都是根据关键字的一位并在前一趟的基础上对所有元素进行排序，直至最高位。

说明：基数排序每趟并不产生有序区，也就是说在最后一趟排序结束前，所有的元素并不一定归位了。

#### 　 2. 基数排序实例 ####

设待排序的表有 10 个元素，其关键字为 \{18,2,20,34,12,32,6,16\}。以下为堆排序的排序过程：

先按个位数进行排序，再按十位数进行排序。

![format_png 14][]

#### 　　3. 排序算法 ####

1 public class RadixSort {     
     2     public static void radixSort(int[] Data){  
     3         int[][] gather = new int[10][Data.length];    //存放某位上数相同值的那一些数，如15 ，25  
     4         int[] sameNumSize = new int[10];               //存放某位相同值的那一些数的个数
     5         int some=0;        //总的收集次数
     6         int sub = 0;      //数组Data的下标
     7         int n=1;          //取低位上的值时的除数，如取个数时n=1，取十位时n=10
     8      
     9         while(some < maxSize(Data)) {  
    10             for(int i = 0; i < Data.length; i++) {    //从个位开始分配
    11                 int remain = (Data[i] / n) % 10;    //取某位上的数  
    12                 gather[remain][sameNumSize[remain]] = Data[i];    //将某位上数相同值的那一些数存放在二维数组gather中
    13                 sameNumSize[remain]++;                //相同值的那一些数的个数加1
    14             }  
    15             
    16             for(int i = 0; i < 10; i++) {    //将分配结束的数收集到源数组中 
    17                 if(sameNumSize[i] != 0) {
    18                     for(int j = 0; j < sameNumSize[i]; j++) {
    19                         Data[sub] = gather[i][j];  
    20                         sub++; 
    21                     }  
    22                     sameNumSize[i] = 0;        //置空，以便下次分配时使用  
    23                 }  
    24             }  
    25             sub = 0;    //下标置0
    26             n *= 10;      //取次低位
    27             some++;      //收集次数加1
    28         }  
    29           
    30     } 
    31     /**
    32      * 求数组中最大数的长度
    33      * @param arr
    34      * @return 最大长度
    35      */
    36     public static int maxSize(int[] arr) {  
    37         int temp = arr[0];  
    38         for(int i = 1;i < arr.length; i++) { 
    39             if(temp < arr[i]) {  
    40                 temp = arr[i];  
    41             }  
    42         }  
    43         return String.valueOf(temp).length();  
    44     } 
    45     
    46     public static void main(String[] args) {
    47         int[] Data = {75,23,98,44,57,12,29,64,38,82};
    48         
    49         radixSort(Data);
    50         System.out.println("基数排序的结果：");
    51         for(int i = 0; i < Data.length; i++) {
    52             System.out.print(Data[i]+" ");
    53         }
    54     }
    55 }

#### 　 4. 算法分析 ####

时间复杂度：O(d(n+r))；

空间复杂度：O(r)；

稳定性：稳定；

复杂性：较复杂。

## 7 各种内排序方法的比较和选择 ##

#### 　 1. 各种排序方法的性能比较 ####

![format_png 15][]

图7.1 各种排序方法的性能比较

#### 　 2. 选择排序方法应综合考虑下列因素： ####

（1）待排序的元素数目 n（问题规模）；

（2）元素的大小（每个元素的规模）；

（3）关键字的结构及其初始状态；

（4）对稳定性的要求；

（5）语言工具的条件；

（6）存储结构；

（7）时间和空间复杂度。

#### 　 3. 总结 ####

（1）若 n 较小（如 n <= 50），可采用直接插入和直接选择排序；

（2）若文件初始状态基本有序（指正序），则应选用直接插入、冒泡或随机的快速排序；

（3）若 n 较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序；

（4）若要将两个有序表组合成一个新的有序表，最好的方法是归并排序方法；

（5）若 n 很大，元素的关键字位数较少且可以分解时，采用基数排序较好。

[format_png]: http://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTExOTA5Ny8yMDE3MDUvMTExOTA5Ny0yMDE3MDUyNDIwNTYzNDg0MS0zMjY4MjY4MTUuanBn?x-oss-process=image/format,png
[format_png 1]: http://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTExOTA5Ny8yMDE3MDUvMTExOTA5Ny0yMDE3MDUwMzE5MDUzNDYwMS01NjE3NTQ4NTEucG5n?x-oss-process=image/format,png
[format_png 2]: http://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTExOTA5Ny8yMDE3MDQvMTExOTA5Ny0yMDE3MDQyMTExMzc0NzMzNy0xNTQzMzQ1Njg4LnBuZw?x-oss-process=image/format,png
[format_png 3]: http://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTExOTA5Ny8yMDE3MDQvMTExOTA5Ny0yMDE3MDQyNjE5MjAxMTY0Ny0zNDY1MzY4NjEucG5n?x-oss-process=image/format,png
[format_png 4]: http://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTExOTA5Ny8yMDE3MDUvMTExOTA5Ny0yMDE3MDUwMjIxMDQzOTcyNi0xMDQ4NzA2NDk2LnBuZw?x-oss-process=image/format,png
[format_png 5]: http://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTExOTA5Ny8yMDE3MDQvMTExOTA5Ny0yMDE3MDQyNjIwMzEyMjQ0NC0xMTU4MDcyNzY5LnBuZw?x-oss-process=image/format,png
[format_png 6]: http://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTExOTA5Ny8yMDE3MDUvMTExOTA5Ny0yMDE3MDUwMjIxMTA0MDUzOS0xODYzMDExMjExLnBuZw?x-oss-process=image/format,png
[format_png 7]: http://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTExOTA5Ny8yMDE3MDUvMTExOTA5Ny0yMDE3MDUwMjIxMTU1NTI3My0xMzg3NjM5ODkwLnBuZw?x-oss-process=image/format,png
[format_png 8]: http://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTExOTA5Ny8yMDE3MDUvMTExOTA5Ny0yMDE3MDUwMzE5MDkwNTk2MS0xODMzNTkxMzU5LnBuZw?x-oss-process=image/format,png
[format_png 9]: http://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTExOTA5Ny8yMDE3MDUvMTExOTA5Ny0yMDE3MDUwMzE5MTAwMTkxNC0xMDQ4MzE3NTgyLnBuZw?x-oss-process=image/format,png
[format_png 10]: http://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTExOTA5Ny8yMDE3MDUvMTExOTA5Ny0yMDE3MDUwMzIxNTUzMzc1Ny0xMzkwNTI1NjI1LnBuZw?x-oss-process=image/format,png
[format_png 11]: http://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTExOTA5Ny8yMDE3MDUvMTExOTA5Ny0yMDE3MDUwMzIwNDEwOTMzNi03MjAzNDgzMjEucG5n?x-oss-process=image/format,png
[format_png 12]: http://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTExOTA5Ny8yMDE3MDUvMTExOTA5Ny0yMDE3MDUwMzIwNDEyMDUwNy0zNDI5Mzg4NzkucG5n?x-oss-process=image/format,png
[format_png 13]: http://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTExOTA5Ny8yMDE3MDUvMTExOTA5Ny0yMDE3MDUwNDIxMDEyMTU3MC0yMDc4MDI3ODM4LnBuZw?x-oss-process=image/format,png
[format_png 14]: http://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTExOTA5Ny8yMDE3MDUvMTExOTA5Ny0yMDE3MDUwNDIxNTc0MzE5NS03NDc1OTY2MjIucG5n?x-oss-process=image/format,png
[format_png 15]: http://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTExOTA5Ny8yMDE3MDUvMTExOTA5Ny0yMDE3MDUwNDIxNTUwMDc4OS0zNDg1ODM3NTUuanBn?x-oss-process=image/format,png