八大排序算法浅析(Java)
关于Java中的排序算法，此篇讨论的都是内部排序，所谓内部排序就是指通过计算机内存来实现的排序
一、选择排序
1、直接选择排序
直接选择排序是每一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
逻辑比较简单，从待排序序列中，找到最小的元素，如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；从余下的个元素中，再找出最小的元素，重复以上步骤，直到排序结束。
public class ChoiceSort {
public static int[] sort(int[] array){
//总共要经过N-1轮比较
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;//记录目前能找到的最小值元素的下标
}
}
//将找到的最小值和i位置所在的值进行交换
if(i != min){
int temp = array[i];
array[i] = array[min];
array[min] = temp;
}
//第i轮排序的结果为
System.out.print("第"+(i+1)+"轮排序后的结果为:");
display(array);
}
return array;
}
public static void display(int[] array){
//...
}
public static void main(String[] args){
int[] array = {4,2,8,9,5,7,6,1,3};
//未排序数组顺序为
System.out.println("未排序数组顺序为：");
display(array);
System.out.println("-----------------------");
array = sort(array);
System.out.println("-----------------------");
System.out.println("经过选择排序后的数组顺序为：");
display(array);
}
}
结果如下
算法分析
- 稳定性：由于在直接选择排序中存在着不相邻元素之间的互换，因此直接选择排序是一种不稳定的排序方法。
- 时间复杂度：第一次内循环比较n - 1次，然后是n-2次，最后一次内循环比较1次。共比较的次数是(n-1)(n-2)+...+1，求等差数列和，得(n-1+1)*n/2=n²/2。舍去最高项系数，其平均时间复杂度为O(n²)。即最好与最坏时间复杂度为O(n²)
- 空间复杂度：O(1)。
2、堆排序
堆是一种特殊的树形数据结构，其每个节点都有一个值，通常提到的堆都是指一颗完全二叉树，根结点的值小于（或大于）两个子节点的值，同时根节点的两个子树也分别是一个堆。
堆排序就是利用堆（假设利用大顶堆）进行排序的方法。它的基本思想是，将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的 n-1 个序列重新构造成一个堆，这样就会得到 n 个元素中次大的值。如此反复执行，便能得到一个有序序列了。
所以算法的关键在于：将一个无序序列构成一个堆；输出堆顶元素后，调整剩余元素成为一个新堆。
实现代码：
public static void adjustHeap(int[] data,int i, int len) {
int temp, j;
temp = data[i];
for (j = 2 * i; j < len; j *= 2) { //沿关键字较大的孩子结点向下筛选
if (j < len && data[j] < data[j + 1]) {
++j; //j为关键字中较大记录的下标
}
if (temp >= data[j]) {
break;
}
data[i] = data[j];
i = j;
}
data[i] = temp;
}
public static int[] heapSort(int[] data) {
int i;
for (i = data.length / 2 - 1; i >= 0; i--) { //构建一个大顶堆
adjustHeap(data, i, data.length - 1);
}
for (i = data.length - 1; i >= 0; i--){ //将堆顶记录和当前未经排序子序列的最后一个记录交换
int temp = data[0];
data[0] = data[i];
data[i] = temp;
adjustHeap(data,0,i-1);
}
return data;
}
算法分析
堆排序的运行时间主要耗费在初始构建堆和在重建堆时反复筛选上。
- 时间复杂度
- 构建堆的时间复杂度为O(n)；在正式排序时，第i次取堆顶记录重建堆需要用O(logi)的时间，并且需要取n-1次堆顶记录，因此重建堆的时间复杂度为O(nlogn)。所以总体来说，堆排序的平均时间复杂度为O(nlog(2)n)，最好、最坏时间复杂度均为O(nlogn)
- 空间复杂度：O(1)
- 记录的比较与交换是跳跃式进行的，因此堆排序也是一种不稳定的排序方法。
二、交换排序
1、冒泡排序
冒泡排序，顾名思义，我们可以联想到一根极细的吸管中有许多泡泡，大泡泡会上浮，小泡泡在底端，底下的泡泡在上浮的过程中如果碰到比自己大的泡泡就不会继续上浮。
所以冒泡排序的规律（从小到大排序的情况下）：从第一个元素开始，从左向右比较相邻的两个元素，如果前者大于后者则交换位置，对每一对相邻元素作同样的工作，直到碰到比自己大的元素或是被交换至最后一个元素，这就是第一次冒泡完成；对第二个起的元素都进行如上操作，除了最后一个元素，直到没有元素满足交换条件即排序完成；
实现代码：
public class BubbleSort {
public static int[] sort(int[] array){
//从第一个元素(下标为0)开始比较，直到最后第二个元素(下标为length-1),一共length-1轮
for(int i = 0 ; i < array.length-1; i++){
//true表示此次循环没有进行交换，排序已经完成。
boolean flag = true;
//对当前无序区间array[0...length-i-1]进行排序
for(int j = 0 ; j < array.length-i-1 ; j++){
if(array[j]>array[j+1]){
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
flag = false;
}
}
if(flag){
break;
}
System.out.print("第"+i+"轮排序后的结果为:");
printArray(array);
}
return array;
}
//遍历显示数组
public static void printArray(int[] array){
for(int i = 0 ; i < array.length ; i++){
System.out.print(array[i]+" ");
}
System.out.println();
}
public static void main(String[] args) {
int[] array = {4,2,8,9,5,7,6,1,3};
//未排序数组顺序为
System.out.println("未排序顺序为：");
printArray(array);
System.out.println("-----------------------");
array = sort(array);
System.out.println("-----------------------");
System.out.println("经过冒泡排序后的顺序为：");
printArray(array);
}
}
结果如下
算法分析
冒泡排序是由两个for循环构成，第一个for循环的变量 i 表示总共需要多少轮比较，第二个for循环的变量 j 表示每轮参与比较的元素下标[0,1，......，length-i]，因为每轮比较都会出现一个最大值放在最右边，所以每轮比较后的元素个数都会少一个，这也是为什么 j 的范围是逐渐减小的。
- 时间复杂度：
- 如果数据正序，只需要走一趟即可完成排序。所需的比较次数C和记录移动次数M均达到最小值，即：Cmin=n-1;Mmin=0;所以，冒泡排序最好的时间复杂度为O(n)。
- 如果数据是反序的，则需要进行n-1趟排序。每趟排序要进行n-i次比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：Cmax = n(n-1)/2 = O(n²) ; Mmax = 3n(n-1)/2 = O(n²)，所以冒泡排序的最坏时间复杂度为：O(n²)。
- 平均时间复杂度为：其外层循环执行 n - 1次。内层循环最多的时候执行N次，最少的时候执行1次，平均执行 (n+1)/2次。 所以循环体内的比较交换约执行 (n - 1)(n + 1) / 2 = (n²- 1)/2。其平均复杂度为O(n²)。
- 空间复杂度为：O(1)
- 冒泡排序是一种稳定的排序算法。
2、快速排序
快速排序是对冒泡排序的一种改进，采用的是分治策略（一般与递归结合使用），以减少排序过程中的比较次数。
首先在数组中选择一个基准点，然后分别从数组的两端扫描数组，设两个指示标志（lo指向起始位置，hi指向末尾)，首先从后半部分开始，如果发现有元素比该基准点的值小，就交换lo和hi位置的值，然后从前半部分开始扫秒，发现有元素大于基准点的值，就交换lo和hi位置的值，如此往复循环，直到lo>=hi,然后把基准点的值放到hi这个位置。一次排序就完成了。以后采用递归的方式分别对前半部分和后半部分排序，当前半部分和后半部分均有序时该数组就自然有序了。
假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一趟快速排序的算法是：
- 设置两个变量I、J，排序开始的时候I：=1，J：=N；
- 以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；
- 从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；
- 从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；
- 重复第3、4步，直到I=J。
具体实例:
划分的过程涉及到三个关键字：“基准元素”、“左游标”、“右游标”
- 基准元素：它是将数组划分为两个子数组的过程中，用于界定大小的值，以它为判断标准，将小于它的数组元素“划分”到一个“小数值的数组”中，而将大于它的数组元素“划分”到一个“大数值的数组”中，这样，我们就将数组分割为两个子数组，而其中一个子数组的元素恒小于另一个子数组里的元素。对于基准元素的选取，原则上是任意的。但是一般我们选取数组中第一个元素为基准元素（假设数组是随机分布的）
- 左游标：它一开始指向待分割数组最左侧的数组元素，在排序的过程中，它将向右移动。
- 右游标：它一开始指向待分割数组最右侧的数组元素，在排序的过程中，它将向左移动。
图示
选取第一个元素 6 作为基准元素。左游标是 i 哨兵，右游标是 j 哨兵
左游标向左移动，右游标向右移动，它们遵循的规则如下：
- 左游标向右扫描，跨过所有小于基准元素的数组元素,直到遇到一个大于或等于基准元素的数组元素， 在那个位置停下。
- 右游标向左扫描，跨过所有大于基准元素的数组元素,直到遇到一个小于或等于基准元素的数组元素，在那个位置停下。
j找到比6小的5停下，i找到比6大的7停下，两者交换后继续前进
同样的操作
ij相遇后，当前位置与基数进行交换，这就是第一次探测。
左边序列为[3,1,2,5,4],右边序列为[9,7,10,8]。接着对于左边序列而言，以数字 3 为基准元素，重复上面的探测操作......
快速排序的每一轮操作就是将基准数字归位，知道所有的数都归位完成，排序就结束了。
实现代码：
public class QuickSort {
//数组array中下标为i和j位置的元素进行交换
private static void swap(int[] array , int i , int j){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
private static void recQuickSort(int[] array,int left,int right){
if(right <= left){
return;//终止递归
}else{
int partition = partitionIt(array,left,right);
recQuickSort(array,left,partition-1);// 对上一轮排序(切分)时，基准元素左边的子数组进行递归
recQuickSort(array,partition+1,right);// 对上一轮排序(切分)时，基准元素右边的子数组进行递归
}
}
private static int partitionIt(int[] array,int left,int right){
//为什么 j加一个1，而i没有加1,是因为下面的循环判断是从--j和++i开始的.
//而基准元素选的array[left],即第一个元素，所以左游标从第二个元素开始比较
int i = left;
int j = right+1;
int pivot = array[left];// pivot 为选取的基准元素（头元素）
while(true){
while(i<right && array[++i] < pivot){}
while(j > 0 && array[--j] > pivot){}
if(i >= j){// 左右游标相遇时候停止， 所以跳出外部while循环
break;
}else{
swap(array, i, j);// 左右游标未相遇时停止, 交换各自所指元素，循环继续
}
}
swap(array, left, j);//基准元素和游标相遇时所指元素交换，为最后一次交换
return j;// 一趟排序完成， 返回基准元素位置(注意这里基准元素已经交换位置了)
}
public static void sort(int[] array){
recQuickSort(array, 0, array.length-1);
}
public static void main(String[] args) {
int[] array = {6,1,2,7,9,3,4,5,10,8};
sort(array);
for(int i : array){
System.out.print(i+" ");
}
}
}
算法分析
- 时间复杂度
- 最优的情况是基准值刚好取在无序区的中间，这样能够最大效率地让两边排序，同时最大地减少递归划分的次数。最好时间复杂度为O(nlogn)。
- 最坏的情况是当每次划分基准值时，得到的基准值总是当前无序区域里最大或最小的那个元素，这种情况下基准值的一边为空，另一边则依然存在着很多元素(仅仅比排序前少了一个)，最坏时间复杂度为：O(n²)。
- 平均时间复杂度为：O(n²)
- 空间复杂度为O(nlogn)
- 快速排序是不稳定的
此排序算法的效率在序列越乱的时候，效率越高。在数据有序时，会退化成冒泡排序；
三、插入排序
1、直接插入排序
直接插入排序是将未排序的数据插入至已排好序序列的合适位置。首先比较数组的前两个数据，并排序；比较第三个元素与前两个排好序的数据，并将第三个元素放入适当的位置；.......比较第n个元素与前面n-1个有序数组，放到适当的位置
代码：
public class InsertSort {
public static int[] sort(int[] array){
int j;
//从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
for(int i = 1 ; i < array.length ; i++){
int tmp = array[i];//记录要插入的数据
j = i;
while(j > 0 && tmp < array[j-1]){//从已经排序的序列最右边的开始比较，找到比其小的数
array[j] = array[j-1];//向后挪动
j--;
}
array[j] = tmp;//存在比其小的数，插入
}
return array;
}
public static void display(int[] array){
//...
}
public static void main(String[] args){
int[] array = {4,2,8,9,5,7,6,1,3};
//未排序数组顺序为
System.out.println("未排序数组顺序为：");
display(array);
System.out.println("-----------------------");
array = sort(array);
System.out.println("-----------------------");
System.out.println("经过插入排序后的数组顺序为：");
display(array);
}
}
算法分析
- 时间复杂度
- 最好的情况，要比较的无序序列原本就是顺序有序的，那么要比较的次数是n-1，移动了0次，最好时间复杂度O(n)
- 最坏的情况，要比较的无序序列原本就是逆序有序的，那么要比较的次数是(n+2)(n-1)/2，移动的次数(n+4)(n-1)/2，最坏时间复杂度O(n²)。
- 直接插入排序的平均复杂度为O(n²)。
- 空间复杂度：O(1)
- 直接插入排序是稳定的
2、希尔排序
与直接插入排序不同的是，希尔排序通过加大插入排序中元素的间隔，并在这些有间隔的元素中进行插入排序，从而使数据项能够大跨度的移动。当这些数据项排过一趟序后，希尔排序算法减小数据项的间隔再进行排序，依次进行下去，最后间隔为1时，就是我们直接插入排序。
希尔的原稿中，他建议间隔选为N/2，也就是每一趟都将排序分为两半，因此对于N=100的数组，逐渐减小的间隔序列为：50,25,12，6,3,1。这个方法的好处是不需要在开始排序前为找到初始序列的间隔而计算序列，只需要用2整除N。但是这已经被证明并不是最好的序列。
还有一种很常用的间隔序列：knuth 间隔序列 3h+1
knuth间隔序列的希尔排序算法代码：
public class InsertSort {
//希尔排序 knuth 间隔序列 3h+1
public static void shellKnuthSort(int[] array){
System.out.println("原数组为"+Arrays.toString(array));
int step = 1 ;
int len = array.length;
while(step <= len/3){
step = step*3 + 1;//1,4,13,40......
}
while(step > 0){
//分别对每个增量间隔进行排序
for(int i = step ; i < len ; i++){
int temp = array[i];
int j = i;
while(j > step-1 && temp <= array[j-step]){
array[j] = array[j-step];
j -= step;
}
array[j] = temp;
}//end for
System.out.println("间隔为"+step+"的排序结果为"+Arrays.toString(array));
step = (step-1)/3;
}//end while(step>0)
System.out.println("最终排序："+Arrays.toString(array));
}
public static void main(String[] args) {
int[] array = {4,2,8,9,5,7,6,1,3};
shellKnuthSort(array);
}
}
结果如下：
一共10个数，即n=10,10<3h-1，h最小时为4，即先以4为间隔，再以1位间隔。
但是无论是什么间隔序列，最后必须满足一个条件，就是逐渐减小的间隔最后一定要等于1，因此最后一趟排序一定是简单的插入排序。
希尔排序并不稳定，空间复杂度为O(1)，用不同的序列，时间复杂度不同，此例中即最坏时间复杂度为O(n²)。最好时间复杂度为O(n)。有人在大量的实验后得出结论;当n在某个特定的范围后希尔排序的比较和移动次数减少至n^1.3 不管增量序列如何取值，都应该满足最后一个增量值为1，平均时间复杂度为O(n^1.3)。
三、归并排序
归并排序与快速排序有一些类似。对于给定的一组记录，利用递归与分治技术将数据序列划分成为越来越小的半子表，在对半子表排序，最后再用递归方法将排好序的半子表合并成为越来越大的有序序列。
先申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；设定两个指针，最初位置分别为两个已经排序序列的起始位置；比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 ；重复前一个步骤直到某一指针达到序列尾；将另一序列剩下的所有元素直接复制到合并序列尾
实现代码：
public static void merge(int[] data, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i= low;// 左指针
int j = mid + 1;// 右指针
int k = 0;
// 把较小的数先移到新数组中
while (i <= mid && j <= high){
if (data[i] < data[j]) {
temp[k++] = data[i++];
}else{
temp[k++] = data[j++];
}
}
// 把左边剩余的数移入数组
while (i <= mid) {
temp[k++] = data[i++];
}
// 把右边边剩余的数移入数组
while (j <= high) {
temp[k++] = data[j++];
}
// 把新数组中的数覆盖nums数组
for (int k2 = 0; k2 < temp.length; k2++){
data[k2 + low] = temp[k2];
}
}
public static void mergeSort(int[] data, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
mergeSort(data, low, mid);//左边
mergeSort(data, mid + 1, high);//右边
merge(data, low, mid, high);//左右归并
}
}
算法分析
- 时间复杂度：一趟归并需要将数组 a[]中相邻的长度为h的有序序列进行两两归并.并将结果放到temp[]中，这需要将待排序列中的所有记录扫描一遍，因此耗费O(n)，而又完全二叉树的深度可知，整个归并排序需要进行log(2)n次，因此平均、最好、最坏时间复杂度为O(nlogn)
- 空间复杂度：归并排序在归并过程中需要与原始序列同样数量的存储空间存放归并结果以及递归时深度为log(2)n的栈空间，因此空间复杂度为O(n+logn)
- merge函数中有if (a[i] < a[j]) 的语句，说明它需要两两比较，不存在跳跃，因此归并排序是一种稳定的排序算法。
归并排序是一种比较占内存，但却效率高且稳定的算法。
四、基数排序
相对于常见的比较排序，基数排序是一种分配式排序，即通过将所有数字分配到应在的位置最后再覆盖到原数组完成排序的过程。
具体先比位数，如果一个位数比另一个位数多，那这个数肯定更大。如果位数同样多，就按位数递减依次往下进行比较，哪个数在这一位上更大那就停止比较，得出这个在这个位上数更大的数字整体更大的结论。也可以从最小的位开始比较，这其实就对应了基数排序里的MSD(most significant digital)和LSD(least significant digital)两种排序方式。
举个例子(LSD)：现在有一个数组73, 22, 93, 43, 55, 14, 28, 65, 39, 81
1、按个位排序，对于十进制数来说基数是10
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
81 |
22 |
73 |
14 |
55 |
28 |
39 |
|||
|
93 |
65 |
||||||||
|
43 |
结果：81,22,73,93,43,14,55,65,28,39
2、结果按百位排序
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
14 |
22 |
39 |
43 |
55 |
65 |
73 |
81 |
93 |
|
|
28 |
取出排序结果：14,22,28,39,43,55,65,73,81,93
实现代码
public class RadixSort {
private static void radixSort(int[] array,int d)
{
int n=1;//代表位数对应的数：1,10,100...
int k=0;//保存每一位排序后的结果用于下一位的排序输入
int length=array.length;
int[][] bucket=new int[10][length];//排序桶用于保存每次排序后的结果，这一位上排序结果相同的数字放在同一个桶里
int[] order=new int[length];//用于保存每个桶里有多少个数字
while(n<d)
{
for(int num:array) //将数组array里的每个数字放在相应的桶里
{
int digit=(num/n)%10;
bucket[digit][order[digit]]=num;
order[digit]++;
}
for(int i=0;i<length;i++)//将前一个循环生成的桶里的数据覆盖到原数组中用于保存这一位的排序结果
{
if(order[i]!=0)//这个桶里有数据，从上到下遍历这个桶并将数据保存到原数组中
{
for(int j=0;j<order[i];j++)
{
array[k]=bucket[i][j];
k++;
}
}
order[i]=0;//将桶里计数器置0，用于下一次位排序
}
n*=10;
k=0;//将k置0，用于下一轮保存位排序结果
}
}
public static void main(String[] args)
{
int[] A=new int[]{73,22, 93, 43, 55, 14, 28, 65, 39, 81};
radixSort(A, 100);
for(int num:A)
{
System.out.println(num);
}
}
}
算法分析
没有任何元素的比较和交换，元素只是在每一轮中从一个队列移动到另一个队列，所以基数排序是稳定的
附：八大排序算法比较
湘公网安备 43102202000103号