Java实现八大排序算法

向右看齐 2021-09-15 00:00 357阅读 0赞

## 概述 ##

排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

我们这里说说八大排序就是内部排序。

![1342514529_5795.jpg][]

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

快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；

> > > ![SouthEast][]

## 1.插入排序—直接插入排序(Straight Insertion Sort)    ##

基本思想:

将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

要点：设立哨兵，作为临时存储和判断数组边界之用。

直接插入排序示例：

![1342520948_8667.jpg][]

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

public class InsertSort { public static void main(String[] args) { int a[]={5,3,9,6,4,1,8,7,2}; Sort sort=new Sort(); System.out.println("排序前:"); sort.print(a); sort.insertSort(a); System.out.println("\n排序后："); sort.print(a); } } class Sort{ public void insertSort(int[] a){ for(int i=1;i<a.length;i++){//从头部第一个当做已经排好序的，把后面的一个一个的插到已经排好的列表中去。 int j; int x=a[i];//x为待插入元素 for(j=i;j>0&&x<a[j-1];j--){//通过循环，逐个后移一位找到要插入的位置 a[j]=a[j-1]; } a[j]=x;//插入 } } public void print(int[] a){ for(int i=0;i<a.length;i++){ System.out.print(a[i]+" "); } } }

运行结果为：

> > 排序前:
> 
> > 5 3 9 6 4 1 8 7 2 
> 
> > 排序后：
> 
> > 1 2 3 4 5 6 7 8 9

效率：时间复杂度：O（n^2）.

## 2. 插入排序—希尔排序（Shell\`s Sort）    ##

希尔排序是1959 年由D.L.Shell 提出来的，相对直接排序有较大的改进。希尔排序又叫缩小增量排序

基本思想：

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

操作方法：

1.  选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2.  按增量序列个数k，对序列进行k 趟排序；
3.  每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

希尔排序的示例：

![1342577299_5077.jpg][]

**给定实例的shell排序的排序过程**  
  
    　假设待排序文件有10个记录，其关键字分别是：  
        49，38，65，97，76，13，27，49，55，04。  
    　增量序列的取值依次为：  
        5，3，1  
    　排序过程如【[动画模拟演示][Link 1]】

算法实现：

我们简单处理增量序列：增量序列d = \{n/2 ,n/4, n/8 .....1\} n为要排序数的个数

即：先将要排序的一组记录按某个增量d（n/2,n为要排序数的个数）分成若干组子序列，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至为1，最后使用直接插入排序完成排序。

public class ShellSort {
    	public static void main(String[] args) {
    		int a[]={5,3,9,6,4,1,8,7,2};
    		Sort1 sort=new Sort1();
    		System.out.println("排序前:");
    		sort.printArray(a);
    		sort.shellInsertSort(a);
    		System.out.println("\n排序后：");
    		sort.printArray(a);
    	}
    }
    
    class Sort1{
    	public void shellInsertSort(int[] a){//类似插入排序，只是插入排序增量是1，这里增量是d,把1换成d就可以了  
    		int j=0;
    		int temp=0;
    		for(int d=a.length/2;d>0;d=d/2){//d是增量
    			for(int i=d;i<a.length;i++){
    				temp=a[i];
    				for(j=i-d;j>=0;j=j-d){
    					if(temp<=a[j]){
    						a[j+d]=a[j];
    					}else{
    						break;
    					}
    				}
    				a[j+d]=temp;
    			}
    		}
    	}
    	public void printArray(int[] a){
    		for(int i=0;i<a.length;i++){
    			System.out.print(a[i]+" ");
    		}
    	}
    }

运行结果为：

> 排序前:
> 
> 5 3 9 6 4 1 8 7 2 
> 
> 排序后：
> 
> 1 2 3 4 5 6 7 8 9

希尔排序时效分析很难，关键码的比较次数与记录移动次数依赖于增量因子序列d的选取，特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法，有取奇数的，也有取质数的，但需要注意：增量因子中除1 外没有公因子，且最后一个增量因子必须为1。希尔排序方法是一个不稳定的排序方法。

## 3. 选择排序—简单选择排序（Simple Selection Sort） ##

基本思想：

在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

简单选择排序的示例：

![1342586432_7130.jpg][]

操作方法：

第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；

第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；

以此类推.....

第i 趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，

直到整个序列按关键码有序。

直接选择排序的过程  
　　对初始关键字为49、38、65、97、76、13、27和49的文件进行直接选择排序的过程【[参见动画演示][Link 2]】

public class Selection {
    	public static void main(String args[]){
    		int a[]={3,1,5,4,8,7,6,9,2};
    		Selection s=new Selection();
    		System.out.println("排序前：");
    		s.print(a);
    		s.selectSort(a);
    		System.out.println("\n排序后：");
    		s.print(a);
    	}
    	public void selectSort(int[] a){
    		for(int i=0;i<a.length;i++){
    			int k=i;
    			for(int j=i+1;j<a.length;j++){
    				if(a[k]>a[j]){
    					k=j;
    				}
    			}
    			swap(a,k,i);
    		}
    	}
    	public void print(int a[]){
    		for(int i=0;i<a.length;i++){
    			System.out.print(a[i]+" ");
    		}
    	}
    	public void swap(int[] data,int i,int j){
    		if(i==j)
    			return;
    		/*//方法一
    		data[i]=data[i]+data[j];
    		data[j]=data[i]-data[j];
    		data[i]=data[i]-data[j];
    		*/
    		/*
    		//方法二
    		int temp;
    		temp=data[i];
    		data[i]=data[j];
    		data[j]=temp;
    		*/
    		//方法三
    		data[i]=data[i]^data[j];
    		data[j]=data[i]^data[j];
    		data[i]=data[i]^data[j];
    	}
    }

运行结果为：

> 排序前:
> 
> 5 3 9 6 4 1 8 7 2 
> 
> 排序后：
> 
> 1 2 3 4 5 6 7 8 9

## 4. 选择排序—堆排序（Heap Sort）    ##

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

基本思想：

堆的定义如下：具有n个元素的序列（k1,k2,...,kn),当且仅当满足

![1342589718_3742.jpg][]

时称之为堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最小项（小顶堆）。  
若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点（堆顶元素）的值是最小(或最大)的。如：

（a）大顶堆序列：（96, 83,27,38,11,09)

(b)  小顶堆序列：（12，36，24，85，47，30，53，91）

> > ![1342592355_2560.jpg][]

> > > ![20180310205631641][]

初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树（一维数组存储二叉树），调整它们的存储序，使之成为一个堆，将堆顶元素输出，得到n 个元素中最小(或最大)的元素，这时堆的根节点的数最小（或者最大）。然后对前面(n-1)个元素重新调整使之成为堆，输出堆顶元素，得到n 个元素中次小(或次大)的元素。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。称这个过程为堆排序。

因此，实现堆排序需解决两个问题：  
1. 如何将n 个待排序的数建成堆；  
2. 输出堆顶元素后，怎样调整剩余n-1 个元素，使其成为一个新堆。

首先讨论第二个问题：输出堆顶元素后，对剩余n-1元素重新建成堆的调整过程。  
调整小顶堆的方法：

1）设有m 个元素的堆，输出堆顶元素后，剩下m-1 个元素。将堆底元素送入堆顶（（最后一个元素与堆顶进行交换），堆被破坏，其原因仅是根结点不满足堆的性质。

2）将根结点与左、右子树中较小元素的进行交换。

3）若与左子树交换：如果左子树堆被破坏，即左子树的根结点不满足堆的性质，则重复方法 （2）.

4）若与右子树交换，如果右子树堆被破坏，即右子树的根结点不满足堆的性质。则重复方法 （2）.

5）继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。

称这个自根结点到叶子结点的调整过程为筛选。如图：

![1342595226_8095.jpg][]

再讨论对n 个元素初始建堆的过程。  
建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。

1）n 个结点的完全二叉树，则最后一个结点是第![1342595562_4106.jpg][]个结点的子树。

2）筛选从第![1342595562_4106.jpg][]个结点为根的子树开始，该子树成为堆。

3）之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。

如图建堆初始过程：无序序列：（49，38，65，97，76，13，27，49）  
                              ![1342596333_5296.jpg][]

![1342596352_2401.jpg][]

算法的实现：

从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。

public class LittleHeapSort {
    	public static void main(String[] args) {
    		 int[] array = {9,3,7,6,8,5,2,1,4};
    		 	Sort4 sort4=new Sort4();
    	        System.out.println("排序前:");
    	        for (int i = 0; i < array.length; i++) {
    	            System.out.print(array[i] + ",");
    	        }
    
    	        System.out.println();
    	        System.out.println("分割线---------------");
    
    	        sort4.heapSort(array);
    
    	        System.out.println("排序后:");
    	        for (int i = 0; i < array.length; i++) {
    	            System.out.print(array[i] + ",");
    	        }
    	}
    }
    class Sort4{
    	public void heapSort(int[] array) {
            if (array == null || array.length == 1)
                return;
    
            buildHeap(array); // 第一次排序，构建最大堆，只保证了堆顶元素是数组里最大的
    
            for (int i = array.length - 1; i >= 1; i--) {
                // 这个是什么意思呢？，经过上面的一些列操作，目前array[0]是当前数组里最大的元素，需要和末尾的元素交换
                // 然后，拿出最大的元素
                swap(array, 0, i);
    
                // 交换完后，下次遍历的时候，就应该跳过最后一个元素，也就是最大的那个值，然后开始重新构建最大堆
                // 堆的大小就减去1，然后从0的位置开始最大堆
               maxHeap(array, i, 0);
               // minHeap(array, i, 0);
            }
        }
    	//构建堆
    	public void buildHeap(int[] array){
    		if(array==null || array.length==1)
    			return;
    		int cursor=array.length/2;
    		for(int i=cursor;i>=0;i--){
    			//minHeap(array, array.length, i);
    			maxHeap(array, array.length, i);
    		}
    	}
    	//最小堆
    	public void minHeap(int[] a,int heapsize,int index){
    		int left=index*2+1;
    		int right=index*2+2;
    		int minvalue=index;
    		if(left<heapsize&&a[left]<a[minvalue]){
    			minvalue=left;
    		}
    		if(right<heapsize && a[right]<a[minvalue]){
    			minvalue=right;
    		}
    		if(minvalue!=index){
    			swap(a,index,minvalue);
    			minHeap(a, heapsize, minvalue);
    		}
    	}
    	//最大堆
    	public void maxHeap(int[] a,int heapsize,int index){
    		int left=2*index+1;
    		int right=2*index+2;
    		int maxvalue=index;
    		if(left<heapsize && a[left]>a[maxvalue]){
    			maxvalue=left;
    		}
    		if(right<heapsize && a[right]>a[maxvalue]){
    			maxvalue=right;
    		}
    		if(maxvalue!=index){
    			swap(a, index, maxvalue);
    			maxHeap(a, heapsize, maxvalue);
    		}
    	}
    	public void swap(int[] a,int i,int j){
    		int temp=a[i];
    		a[i]=a[j];
    		a[j]=temp;
    	}
    }

运行结果为：

> 排序前:
> 
> 9,3,7,6,8,5,2,1,4,
> 
> 分割线---------------
> 
> 排序后:
> 
> 1,2,3,4,5,6,7,8,9,

## 5. 交换排序—冒泡排序（Bubble Sort） ##

基本思想：

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

冒泡排序的示例：

![1342782078_9990.jpg][]

2、冒泡排序过程示例  
    　对关键字序列为49 38 65 97 76 13 27 49的文件进行冒泡排序的过程【[参见动画演示][Link 3]】

**算法的实现：**

public class BubbleSort {
    	public static void main(String[] args) {
    		int[] a={9,3,7,6,8,5,2,1,4};
    		Sort5 sort=new Sort5();
    		System.out.println("排序前:");
    		sort.print(a);
    		sort.bubbleSort1(a);
    		System.out.println("\n排序后：");
    		sort.print(a);
    	}
    }
    class Sort5{
    	//冒泡排序方法一
    	public void bubbleSort(int[] a){
    		for(int i=0;i<a.length;i++){
    			for(int j=0;j<a.length-1-i;j++){
    				if(a[j]>a[j+1]){
    					int temp=a[j];
    					a[j]=a[j+1];
    					a[j+1]=temp;
    				}
    			}
    		}
    	}
    	
    	//冒泡排序方法二  
        public void bubbleSort1(int[] arr){  
            for(int x=arr.length-1;x>0;x--){  
                for(int y=0;y<x;y++){  
                    if(arr[y]>arr[y+1]){  
                        int temp=arr[y];  
                        arr[y]=arr[y+1];  
                        arr[y+1]=temp;  
                    }  
                }  
            }  
        }  
    	public void print(int[] a){
    		for(int i=0;i<a.length;i++){
    			System.out.print(a[i]+" ");
    		}
    	}
    }

运行结果为：

> 排序前:
> 
> 9 3 7 6 8 5 2 1 4 
> 
> 排序后：
> 
> 1 2 3 4 5 6 7 8 9

## 6. 交换排序—快速排序（Quick Sort） ##

基本思想：

1）选择一个基准元素,通常选择第一个元素或者最后一个元素,

2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。

3）此时基准元素在其排好序后的正确位置

4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

快速排序的示例：

（a）一趟排序的过程：

![1342782317_4426.jpg][]

（b）排序的全过程

![1342782329_8314.jpg][]

**算法的实现：**

package com.suanfa;
    
    public class QuickSort {
    	public static void main(String[] args) {
    		int[] a={9,3,7,6,8,5,2,1,4};
    		int start=0;
    		int end=a.length-1;
    		Sort6 sort=new Sort6();
    		System.out.println("排序前:");
    		sort.print(a);
    		sort.quickSort(a, start, end);
    		System.out.println("\n排序后：");
    		sort.print(a);
    	}
    }
    class Sort6{
    	public void quickSort(int[] arr,int low,int high){
    		int start=low;
    		int end=high;
    		int key=arr[low];
    		while(start<end){
    			//从后往前开始比较
    			while(end>start && arr[end]>=key)//如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
    				end--;
    			if(arr[end]<=key){
    				int temp=arr[end];
    				arr[end]=arr[start];
    				arr[start]=temp;
    			}
    			//从前往后比较
    			while(end>start && arr[start]<=key){//如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置，然后又从后往前比较
    				start++;
    			}
    			if(arr[start]>=key){
    				int temp=arr[end];
    				arr[end]=arr[start];
    				arr[start]=temp;
    			}
    			//此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用  
    		}
    		//递归
    		if(start>low)
    			quickSort(arr, low, start-1);
    		if(start<high)
    			quickSort(arr, end+1, high);
    	}
    	
    	public void print(int[] a){
    		for(int i=0;i<a.length;i++){
    			System.out.print(a[i]+" ");
    		}
    	}
    }

运行结果为：

> 排序前:
> 
> 9 3 7 6 8 5 2 1 4 
> 
> 排序后：
> 
> 1 2 3 4 5 6 7 8 9

## 7. 归并排序（Merge Sort） ##

基本思想：

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序示例：

![1342842633_6751.jpg][]

合并方法：

设r\[i…n\]由两个有序子表r\[i…m\]和r\[m+1…n\]组成，两个子表长度分别为n-i +1、n-m。

1.  j=m+1；k=i；i=i; //置两个子表的起始下标及辅助数组的起始下标
2.  若i>m 或j>n，转⑷ //其中一个子表已合并完，比较选取结束
3.  //选取r\[i\]和r\[j\]较小的存入辅助数组rf  
    如果r\[i\]<r\[j\]，rf\[k\]=r\[i\]； i++； k++； 转⑵  
    否则，rf\[k\]=r\[j\]； j++； k++； 转⑵
4.  //将尚未处理完的子表中元素存入rf  
    如果i<=m，将r\[i…m\]存入rf\[k…n\] //前一子表非空  
    如果j<=n ,  将r\[j…n\] 存入rf\[k…n\] //后一子表非空
5.  合并结束。

import java.net.Inet4Address;
    
    public class MergeSort {
    	public static void main(String[] args) {
    		int[] a={9,3,7,6,8,5,2,1,4};
    		Sort7 sort=new Sort7();
    		System.out.println("排序前:");
    		sort.print(a);
    		sort.mergeSort(a);
    		System.out.println("\n排序后：");
    		sort.print(a);
    	}
    }
    class Sort7{
    	public void mergeSort(int[] arr){
    		sort(arr, 0, arr.length-1);
    	}
    	public void sort(int[] arr,int start,int end){
    		if(start>=end)
    			return;
    		//找出中间索引
    		int center=(start+end)/2;
    		//对左边数组进行递归
    		sort(arr, start, center);
    		//对右边数组进行递归
    		sort(arr, center+1, end);
    		//合并
    		merge(arr,start,center,end);
    	}
    	public void merge(int[] arr,int start,int center,int end){
    		//临时数组
    		int[] temp=new int[arr.length];
    		//右数组第一个元素索引
    		int mid=center+1;
    		//third记录临时数组的索引
    		int third = start;   
    		int tmp=start;
    		while(start<=center && mid<=end){
    			// 从两个数组中取出最小的放入临时数组    
                if (arr[start] <= arr[mid]) {    
                    temp[third++] = arr[start++];    
                } else {    
                    temp[third++] = arr[mid++];    
                }    
    		}
    		// 剩余部分依次放入临时数组（实际上两个while只会执行其中一个）    
            while (mid <= end) {    
                temp[third++] = arr[mid++];    
            }    
            while (start <= center) {    
                temp[third++] = arr[start++];    
            }    
            // 将临时数组中的内容拷贝回原数组中    
            // （原left-right范围的内容被复制回原数组）    
            while (tmp <= end) {    
                arr[tmp] = temp[tmp++];    
            }    
    	}
    	public void print(int[] a){
    		for(int i=0;i<a.length;i++){
    			System.out.print(a[i]+" ");
    		}
    	}	
    }

运行结果为：

> 排序前:
> 
> 9 3 7 6 8 5 2 1 4 
> 
> 排序后：
> 
> 1 2 3 4 5 6 7 8 9

## 8. 桶排序/基数排序(Radix Sort) ##

说基数排序之前，我们先说桶排序：

基本思想：是将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。  
         简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。

例如要对大小为\[1..1000\]范围内的n个整数A\[1..n\]排序

首先，可以把桶设为大小为10的范围，具体而言，设集合B\[1\]存储\[1..10\]的整数，集合B\[2\]存储   (10..20\]的整数，……集合B\[i\]存储(   (i-1)\*10,   i\*10\]的整数，i   =   1,2,..100。总共有  100个桶。

然后，对A\[1..n\]从头到尾扫描一遍，把每个A\[i\]放入对应的桶B\[j\]中。  再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任  何排序法都可以。

最后，依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这  样就得到所有数字排好序的一个序列了。

假设有n个数字，有m个桶，如果数字是平均分布的，则每个桶里面平均有n/m个数字。如果

对每个桶中的数字采用快速排序，那么整个算法的复杂度是

O(n   +   m   \*   n/m\*log(n/m))   =   O(n   +   nlogn   -   nlogm)

从上式看出，当m接近n的时候，桶排序复杂度接近O(n)

当然，以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的  ，实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中，那就退化成一般的排序了。

前面说的几大排序算法 ，大部分时间复杂度都是O（n2），也有部分排序算法时间复杂度是O(nlogn)。而桶式排序却能实现O（n）的时间复杂度。但桶排序的缺点是：

1）首先是空间复杂度比较高，需要的额外开销大。排序有两个数组的空间开销，一个存放待排序数组，一个就是所谓的桶，比如待排序值是从0到m-1，那就需要m个桶，这个桶数组就要至少m个空间。

2）其次待排序的元素都要在一定的范围内等等。

桶式排序是一种分配排序。分配排序的特定是不需要进行关键码的比较，但前提是要知道待排序列的一些具体情况。

分配排序的基本思想：说白了就是进行多次的桶式排序。

基数排序过程无须比较关键字，而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶：O(n)。

基数排序的排序过程  
    　要排序的记录关键字取值范围是0到99之间的整数(36，5，16，98，95，47， 32，36，48)。对这些关键字进行基数排序的过程【[参见动画演示][Link 4]】。

实例:

扑克牌中52 张牌，可按花色和面值分成两个字段，其大小关系为：  
花色： 梅花< 方块< 红心< 黑心  ![1342855666_4899.jpg][]  
面值： 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A

若对扑克牌按花色、面值进行升序排序，得到如下序列：  
![1342855525_3489.jpg][]

![1342855538_2075.jpg][]

即两张牌，若花色不同，不论面值怎样，花色低的那张牌小于花色高的，只有在同花色情况下，大小关系才由面值的大小确定。这就是多关键码排序。

为得到排序结果，我们讨论两种排序方法。  
方法1：先对花色排序，将其分为4 个组，即梅花组、方块组、红心组、黑心组。再对每个组分别按面值进行排序，最后，将4 个组连接起来即可。  
方法2：先按13 个面值给出13 个编号组(2 号，3 号，...，A 号)，将牌按面值依次放入对应的编号组，分成13 堆。再按花色给出4 个编号组(梅花、方块、红心、黑心)，将2号组中牌取出分别放入对应花色组，再将3 号组中牌取出分别放入对应花色组，……，这样，4 个花色组中均按面值有序，然后，将4 个花色组依次连接起来即可。

设n 个元素的待排序列包含d 个关键码\{k1，k2，…，kd\}，则称序列对关键码\{k1，k2，…，kd\}有序是指：对于序列中任两个记录r\[i\]和r\[j\](1≤i≤j≤n)都满足下列有序关系：

![1342829730_4247.jpg][]

其中k1 称为最主位关键码，kd 称为最次位关键码     。

两种多关键码排序方法：

多关键码排序按照从最主位关键码到最次位关键码或从最次位到最主位关键码的顺序逐次排序，分两种方法：

最高位优先(Most Significant Digit first)法，简称MSD 法：

1）先按k1 排序分组，将序列分成若干子序列，同一组序列的记录中，关键码k1 相等。

2）再对各组按k2 排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd 对各子组排序后。

3）再将各组连接起来，便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法一即是MSD 法。

最低位优先(Least Significant Digit first)法，简称LSD 法：

1) 先从kd 开始排序，再对kd-1进行排序，依次重复，直到按k1排序分组分成最小的子序列后。

2) 最后将各个子序列连接起来，便可得到一个有序的序列, 扑克牌按花色、面值排序中介绍的方法二即是LSD 法。

基于LSD方法的链式基数排序的基本思想

“多关键字排序”的思想实现“单关键字排序”。对数字型或字符型的单关键字，可以看作由多个数位或多个字符构成的多关键字，此时可以采用“分配-收集”的方法进行排序，这一过程称作基数排序法，其中每个数字或字符可能的取值个数称为基数。比如，扑克牌的花色基数为4，面值基数为13。在整理扑克牌时，既可以先按花色整理，也可以先按面值整理。按花色整理时，先按红、黑、方、花的顺序分成4摞（分配），再按此顺序再叠放在一起（收集），然后按面值的顺序分成13摞（分配），再按此顺序叠放在一起（收集），如此进行二次分配和收集即可将扑克牌排列有序。

基数排序:

是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

参考：

## [http://student.zjzk.cn/course\_ware/data\_structure/web/paixu/paixu8.7.1.1.htm][http_student.zjzk.cn_course_ware_data_structure_web_paixu_paixu8.7.1.1.htm] ##

[1342514529_5795.jpg]: https://img-my.csdn.net/uploads/201207/17/1342514529_5795.jpg
[SouthEast]: /images/20210720/b683b56c418842bb90597ecf6d93313b.png
[1342520948_8667.jpg]: https://img-my.csdn.net/uploads/201207/17/1342520948_8667.jpg
[1342577299_5077.jpg]: https://img-my.csdn.net/uploads/201207/18/1342577299_5077.jpg
[Link 1]: http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/shell.htm
[1342586432_7130.jpg]: https://img-my.csdn.net/uploads/201207/18/1342586432_7130.jpg
[Link 2]: http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/zhijiexuanze.htm
[1342589718_3742.jpg]: https://img-my.csdn.net/uploads/201207/18/1342589718_3742.jpg
[1342592355_2560.jpg]: https://img-my.csdn.net/uploads/201207/18/1342592355_2560.jpg
[20180310205631641]: /images/20210720/a02a441265824c23adc695dbc3e96a15.png
[1342595226_8095.jpg]: https://img-my.csdn.net/uploads/201207/18/1342595226_8095.jpg
[1342595562_4106.jpg]: https://img-my.csdn.net/uploads/201207/18/1342595562_4106.jpg
[1342596333_5296.jpg]: https://img-my.csdn.net/uploads/201207/18/1342596333_5296.jpg
[1342596352_2401.jpg]: https://img-my.csdn.net/uploads/201207/18/1342596352_2401.jpg
[1342782078_9990.jpg]: https://img-my.csdn.net/uploads/201207/20/1342782078_9990.jpg
[Link 3]: http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/maopaopaixu.htm
[1342782317_4426.jpg]: https://img-my.csdn.net/uploads/201207/20/1342782317_4426.jpg
[1342782329_8314.jpg]: https://img-my.csdn.net/uploads/201207/20/1342782329_8314.jpg
[1342842633_6751.jpg]: https://img-my.csdn.net/uploads/201207/21/1342842633_6751.jpg
[Link 4]: http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/jishupaixu.htm
[1342855666_4899.jpg]: https://img-my.csdn.net/uploads/201207/21/1342855666_4899.jpg
[1342855525_3489.jpg]: https://img-my.csdn.net/uploads/201207/21/1342855525_3489.jpg
[1342855538_2075.jpg]: https://img-my.csdn.net/uploads/201207/21/1342855538_2075.jpg
[1342829730_4247.jpg]: https://img-my.csdn.net/uploads/201207/21/1342829730_4247.jpg
[http_student.zjzk.cn_course_ware_data_structure_web_paixu_paixu8.7.1.1.htm]: http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.7.1.1.htm