内部排序总结

以你之姓@ 2022-07-26 13:09 137阅读 0赞

**内部排序总结**

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。

以下对排序算法进行整理，使用的编程语言是Java。

1) 插入排序：(1)直接插入排序，(2)折半插入排序，(3)2路插入排序，(4)希尔排序。

2)交换排序：(1)冒泡排序，(2)快速排序。

3)选择排序：(1)直接选择排序，(2)树形选择排序，(3)堆排序。

4)归并排序。

5)基数排序。

6)计数排序；桶排序。

**1.直接插入排序：**将一个记录插入到有序表中的恰当位置，从而得到一个新的记录数增1的有序表。对于第一个记录，直接放置即可，从第二个记录开始执行其基本操作，直到所有记录都插入到有序表中。

操作过程如下图：

![SouthEast][]

直接插入排序InsertSort代码：

package sort;
    /** 
     * @author  WuPing
     * @date 2016年4月2日 下午11:44:26 
     * @version 1.0 
     * @parameter  
     * @since  
     * @return  
     */
    public class InsertSort {
    	public static void insertSort(int[] array) {
    		if (array != null && array.length != 0) {
    			//假设第一个数位置时正确的；要往后移，必须要假设第一个。 
    			for (int i = 1; i < array.length; i++) {   
    				int j = i;
    				int target = array[i];
    				//后移  
    	            while(j > 0 && target < array[j-1]) {  
    	            	array[j] = array[j-1];  
    	                j--;  
    	            }  
    	            //插入   
    	            array[j] = target; 
    			}
    		}
    	}
    }

**2.** **折半插入排序：**折半插入排序是对直接插入排序的改进，折半插入排序在查找插入位置时，采用折半查找方法，而不是顺序查找方法。

折半插入排序BinaiSort代码：

package sort;
    /** 
     * @author  WuPing
     * @date 2016年4月10日 下午6:48:37 
     * @version 1.0 
     * @parameter  
     * @since  
     * @return  
     */
    public class BinaiSort {
       //array为已排序的数组，i为待插入的记录，length为已排序数组的长度
       public static void binaiPass(int[] array, int i, int length){
    	   int insertNote = i;  //设置监视哨
    	   int low = 0;     //初始化搜索的边界
    	   int high = length;
    	   
    	   //查找待插入位置
    	   while(low<=high){
    		   int mid = (low+high)/2;    //找出中间值
    		   if(insertNote>array[mid])  //在大于中间值的那部分查找
    		       low = mid + 1;
    		   else                       
    			   high = mid - 1;        //在小于中间值的那部分查找
    	   }
    	   
    	   //后移插入位置后的记录，留出空位
    	   for(int j=length+1; j>low; j--){
    		   array[j]=array[j-1];
    	   }
    	   //将记录插入到适当的位置
    	   array[low]=insertNote;
       }
       
       public static void binaiSort(int[] array){
    	   if (array != null && array.length != 0) {
    		   for(int i=1; i<array.length; i++){
    			   binaiPass(array, array[i], i-1);
    		   }
    	   }
       }
    }

**3. 2路****插入排序：**前面讲的折半插入排序是针对直接排序中比较记录关键字这个基本操作进行的优化，而2路插入排序则是在折半排序的基础上对移动记录这个基本操作进行的优化。

2路插入排序的做法是用待排序的序列的第一个记录record\[1\]将排序任务分成两部分，第一部分的所有记录比record\[1\]小，第二部分的所有记录都比record\[1\]大。这样将一个较大的排序任务，分解成两个较小的排序任务，从而减少了记录的移动次数。

操作过程如下图：

![SouthEast 1][]

2路插入排序TwoSort代码：

package sort;
    
    /**
     * @author WuPing
     * @date 2016年4月10日 下午10:03:45
     * @version 1.0
     * @parameter
     * @since
     * @return 
     */
    public class TwoSort {
    	public static void twoSort(int[] array) {
    		if (array == null || array.length == 0) 
    			return;
    		
    		int first = 0; 
    		int last = 0;
    		int length = array.length;
    		int[] aim = new int[length];
    		aim[0] = array[0];
    		for (int i = 1; i < length; i++) {
    			if (array[i] < aim[first]) {      //小于当前最小值,前插  
    				first = (first - 1 + length) % length;
    				aim[first] = array[i];
    			} else if (array[i] > aim[last]) {  //大于当前最大值,后插  
    				last++;
    				aim[last] = array[i];
    			} else {   //大于当前最小值，小于当前最大值，中间插  
    				int low, high, mid, n;
    				low = first;
    				high = last;
    				while (low != high)  //折半查找
    				{
    					n = (high - low + length) % length;  //元素个数
    					mid = (low + n / 2) % length; // 中间位置
    					if (array[i] < aim[mid])
    						high = mid;
    					else
    					    low = (mid + 1) % length;
    				}
    				for (int j = last + 1; j != low; j = (j - 1 + length) % length){
    					// 移动元素
    					aim[j] = aim[(j - 1 + length) % length];
    				}
    				aim[low] = array[i];
    				last++;
    			}
    		}
    		//将已排好序的数组复制到原数组
    		for (int i = 0; i < length; i++) {
    			array[i] = aim[(i + first) % length];
    		}
    	}
    }

**4.****希尔排序：** 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。

操作过程如下图：

![SouthEast 2][]

希尔排序ShellSort代码：

package sort;
    
    /**
     * @author WuPing
     * @date 2016年4月10日 上午10:06:29
     * @version 1.0
     * @parameter d 增量
     * @since
     * @return
     */
    public class ShellSort {
    	public static void shellPass(int[] array, int d) {
    		for (int i = d; i < array.length; i++) {
    			int j = i - d;
    			int temp = array[i]; // 记录要插入的数据
    			while (j >= 0 && array[j] > temp) { // 从后向前，找到比其小的数的位置
    				array[j + d] = array[j]; // 向后挪动
    				j -= d;
    			}
    			if (j != i - d) // 存在比其小的数
    				array[j + d] = temp;
    		}
    	}
    
    	public static void shellSort(int[] array) {
    		if (array != null && array.length != 0) {
    			int d = array.length / 2;
    			while (d >= 1) {
    				shellPass(array, d);
    				d /= 2;
    			}
    		}
    	}
    }

**5.****冒泡排序：** 冒泡排序算法的步骤如下：

①比较相邻的元素。如果第一个比第二个大，就交换他们两个。  
②对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。  
③针对所有的元素重复以上的步骤，除了最后一个。  
④持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

冒泡排序BubbleSort代码：

package sort;
    
    /** 
     * @author  WuPing
     * @date 2016年4月2日 下午9:40:44 
     * @version 1.0 
     * @parameter  
     * @since  
     * @return  
     */
    
    public class BubbleSort {
    
       public static void bubbleSort(int[] array)
       {
    	   if(array!=null&&array.length!=0){
    	     for(int i=0; i<array.length-1; i++){
    		     for(int j=array.length-1; j>i; j--){
    			    if(array[j]<array[j-1]){
    				   int temp = array[j];
    				   array[j] = array[j-1];
    				   array[j-1] = temp;
    			    }
    		    }
    	     }
    	   }
       }
    }

6.快速排序(Quicksort)：是对冒泡排序的一种改进。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序QuickSort代码：

package sort;
    /** 
     * @author  WuPing
     * @date 2016年4月2日 下午11:57:28 
     * @version 1.0 
     * @parameter  
     * @since  
     * @return  
     */
    public class QuickSort {
    	//一次划分
    	public static int partition(int[] array, int left, int right) {
            int pivotKey = array[left];
            while(left < right) {
                while(left < right && array[right] >= pivotKey)
                    right --;
                array[left] = array[right];    //把小的移动到左边
                while(left < right && array[left] <= pivotKey)
                    left ++;
                array[right] = array[left];    //把大的移动到右边
            }
            array[left] = pivotKey;  //最后把pivot赋值到中间
            return left;
        }
        
        //递归划分子序列
        public static void quickSort(int[] array, int left, int right) {
            if(left >= right)
                return ;
            int pivotPos = partition(array, left, right);
            quickSort(array, left, pivotPos-1);
            quickSort(array, pivotPos+1, right);
        }
        
        public static void sort(int[] array) {
            if(array != null && array.length != 0){
              quickSort(array, 0, array.length-1);
            }
        }
    	
    }

**7.直接选择排序：**  
 直接选择排序(Straight Select Sorting) 也是一种简单的排序方法，它的基本思想是：第一次从R\[0\]~R\[n-1\]中选取最小值，与R\[0\]交换；第二次从R\[1\]~R\[n-1\]中选取最小值，与R\[1\]交换；....，第i次从R\[i-1\]~R\[n-1\]中选取最小值，与R\[i-1\]交换；.....，第n-1次从R\[n-2\]~R\[n-1\]中选取最小值，与R\[n-2\]交换。总共通过n-1次，得到一个按排序码从小到大排列的有序序列。

直接选择排序SelectSort代码：

package sort;
    /** 
     * @author  WuPing
     * @date 2016年4月2日 下午10:58:52 
     * @version 1.0 
     * @parameter  
     * @since  
     * @return  
     */
    public class SelectSort {
    
    	public static void selectSort(int[] array){
    		if(array!=null&&array.length!=0){
    		  int minIndex=0;
    		  for(int i=0; i<array.length-1; i++){ //只需要比较n-1次  
    			 minIndex=i;
    			 for(int j=i+1; j<array.length; j++){  //从i+1开始比较，因为minIndex默认为i了，i就没必要比了。 
    				 if(array[j]<array[minIndex]){
    					minIndex=j;
    				 }
    			 }
    			 if(minIndex!=i){  //如果minIndex不为i，说明找到了更小的值，交换之。  
    				 int temp = array[i];
    				 array[i] = array[minIndex];
    				 array[minIndex] = temp;
    			 } 
    	     }
    	   }
    	}
    }

**8.树形****选择排序**： 树形选择排序又称锦标赛 排序（Tournament Sort），是一种按照锦标赛的思想进行选择排序的方法。首先对n个记录的关键字进行两两比较，然后在n/2个较小者之间再进行两两比较，如此重复，直至选出最小的记录为止。

实现原理：

第一步，首先对n个记录进行两两比较，得到较小的n/2个数再依次比较，依次类推直到得到一个最小值,这是一个构造完全二叉树的过程，根节点即为最小元素，叶子节点为列表元素。  
构造的此树的存储结构可以用数组表示方法，数组长度为2n-1。填充此树，比如  
列表元素为：49 38 65 97 76 13 27 49  
构造的树为： 13  
38 13  
38 65 13 27  
19 38 65 97 76 13 27 49  
13为根结点位最小值，列表元素为叶子节点 。  
第二步，移走最小元素，此时可重新为数组a的第一个位置赋值为此最小值，之后如果找出次小值则可以为第二个位置赋值，......  
第三步，找出次小值，找出最小值在叶子节点的位置，从该节点开始，和其兄弟节点进行比较，修改从叶子节点到根节点的元素值，比较完毕后，根节点为次小值。 第三步比较是利用了第一次比较提供的信息，因为第一步已经得到了两两比较的较小值，只要拿第一次与最小值比较的元素(即最小值的兄弟节点)与它们比较即可得最小值。  
即拿上述例子的76与27比较，然后27与38比较得到次小值27。  
重复第二和第三步，排序完成。  
PS:这里把移出去的叶子节点都要重设为最大值，可对此方法进行稍微改动可传一个最大值进来，这里是整型所以用了Integer.MAX\_VALUE 。

树形选择排序 TreeSelectSort 代码：

package sort;
    /** 
     * @author  WuPing
     * @date 2016年4月10日 下午11:32:35 
     * @version 1.0 
     * @parameter  
     * @since  
     * @return  
     */
    public class TreeSelectSort {
        public static void treeSelectSort(int[] array){    
           int length = array.length;  
           int treeSize = 2 * length - 1;  //完全二叉树的节点数  
           int low = 0;  
           int[] tree = new int[treeSize];     //临时的树存储空间  
           //由后向前填充此树，索引从0开始  
           for(int i=length-1,j=0; i>=0; --i,j++){   //填充叶子节点  
               tree[treeSize-1-j] = array[i];  
           }  
             
           for(int i = treeSize-1;i>0;i-=2){ //填充非终端节点  
               tree[(i-1)/2] = tree[i-1] < tree[i] ? tree[i-1]:tree[i];  
           }  
             
           //不断移走最小节点  
           int minIndex;  
           while(low < length){  
               int min = tree[0];    //最小值  
               array[low++] = min;  
               minIndex = treeSize-1;         
               //找到最小值的索引  
               while(tree[minIndex]!=min){  
                   minIndex--;  
               }  
               tree[minIndex] = Integer.MAX_VALUE;  //设置一个最大值标志  
               //找到其兄弟节点  
               while(minIndex > 0){      //如果其还有父节点  
                   if(minIndex % 2 == 0){   //如果是右节点  
                       tree[(minIndex-1)/2] = tree[minIndex-1] < tree[minIndex] ? tree[minIndex-1]:tree[minIndex];  
                       minIndex = (minIndex-1)/2;  
                   }else{                   //如果是左节点  
                        tree[minIndex/2] = tree[minIndex] < tree[minIndex+1] ? tree[minIndex]:tree[minIndex+1];  
                        minIndex = minIndex/2;  
                   }  
               }    
           }  
        }  
    }

**9.堆排序：**  
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构 所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A\[PARENT\[i\]\] >= A\[i\]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

堆排序HeapSort代码：

package sort;
    /** 
     * @author  WuPing
     * @date 2016年4月4日 下午10:45:09 
     * @version 1.0 
     * @parameter  
     * @since  
     * @return  
     */
    public class HeapSort {
    	
    	public static void swap(int[] array, int i, int j) {  
               int temp = array[i];  
               array[i] = array[j];  
               array[j] = temp;  
            } 
    	
    	/** 
         * 堆筛选，除了start之外，start~end均满足大顶堆的定义。 
         * 调整之后start~end称为一个大顶堆。 
         * @param arr 待调整数组 
         * @param start 起始指针 
         * @param end 结束指针 
         */  
        public static void heapAdjust(int[] array, int start, int end) {  
            int temp = array[start];  
            for(int i=2*start+1; i<=end; i*=2) {  
                //左右孩子的节点分别为2*i+1,2*i+2  
                //选择出左右孩子较小的下标  
                if(i < end && array[i] < array[i+1]) {  
                    i++;   
                }  
                if(temp >= array[i]) {  
                    break;  //已经为大顶堆，保持稳定性。  
                }  
                array[start] = array[i];  //将子节点上移  
                start = i;  //下一轮筛选  
            }  
            array[start] = temp; //插入正确的位置  
        }  
      
        public static void heapSort(int[] array) {  
            if(array != null && array.length != 0) {  
            	//建立大顶堆  
                for(int i=array.length/2; i>=0; i--) {  
                    heapAdjust(array, i, array.length-1);  
                }  
                for(int i=array.length-1; i>=0; i--) {  
                    swap(array, 0, i);  
                    heapAdjust(array, 0, i-1);  
                }    
            }
        }  
    }

**10.归并排序：**

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并过程为：比较a\[i\]和a\[j\]的大小，若a\[i\]≤a\[j\]，则将第一个有序表中的元素a\[i\]复制到r\[k\]中，并令i和k分别加上1；否则将第二个有序表中的元素a\[j\]复制到r\[k\]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间\[s,t\]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间\[s,t\]。

归并排序 MergeSort 代码：

package sort;
    /** 
     * @author  WuPing
     * @date 2016年4月10日 上午10:29:06 
     * @version 1.0 
     * @parameter  
     * @since  
     * @return  
     */
    public class MergeSort {
        public static void mergeSort(int[] array) {  
           mSort(array, 0, array.length-1);  
        }  
      
        /** 
         * 递归分治 
         * @param array 待排数组 
         * @param left 左指针 
         * @param right 右指针 
         */  
        public static void mSort(int[] array, int left, int right) {  
            if(left < right)  {
            	int mid = (left + right) / 2;  
                mSort(array, left, mid);  //递归排序左边  
                mSort(array, mid+1, right);  //递归排序右边  
                merge(array, left, mid, right);  //合并  
            }
        }  
          
        /** 
         * 合并两个有序数组 
         * @param array 待合并数组 
         * @param left 左指针 
         * @param mid 中间指针 
         * @param right 右指针 
         */  
        public static void merge(int[] array, int left, int mid, int right) {    
            int[] temp = new int[right - left + 1];  //中间数组  
              
            int i = left;  
            int j = mid + 1;  
            int k = 0;  
            while(i <= mid && j <= right) {  
            	temp[k++] = array[i] <= array[j] ? array[i++] : array[j++];
            }  
              
            while(i <= mid) {  
                temp[k++] = array[i++];  
            }  
              
            while(j <= right) {  
                temp[k++] = array[j++];  
            }  
              
            for(int p=0; p<temp.length; p++) {  
            	array[left + p] = temp[p];  
            }  
        }  
    }

**11.基数排序：**  
基数排序（radix sort）属于“分配式排序”（distribution sort）。顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，在某些时候，基数排序法的效率高于其它的稳定性排序法。基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机(Tabulation Machine)上的贡献。它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

基数排序RadixSort代码：

package sort;
    
    import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    
    /** 
     * @author  WuPing
     * @date 2016年4月10日 下午3:39:06 
     * @version 1.0 
     * @parameter  
     * @since  
     * @return  
     */
    public class RadixSort {
    	public static void radixSort(int[] array) {
            if(array != null && array.length != 0){
            	int maxBit = getMaxBit(array);
                for(int i=1; i<=maxBit; i++) {
                    List<List<Integer>> buf = distribute(array, i);  //分配
                    collecte(array, buf); //收集
                }
            }
        }
        
        /**
         * 分配
         * @param array 待分配数组
         * @param iBit 要分配第几位
         * @return
         */
        public static List<List<Integer>> distribute(int[] array, int iBit) {
            List<List<Integer>> buf = new ArrayList<List<Integer>>();
            for(int j=0; j<10; j++) {
                buf.add(new LinkedList<Integer>());
            }
            for(int i=0; i<array.length; i++) {
                buf.get(getNBit(array[i], iBit)).add(array[i]);
            }
            return buf;
        }
        
        /**
         * 收集
         * @param array 把分配的数据收集到array中
         * @param buf 
         */
        public static void collecte(int[] array, List<List<Integer>> buf) {
            int k = 0;
            for(List<Integer> bucket : buf) {
                for(int element : bucket) {
                	array[k++] = element;
                }
            }
        }
        
        /**
         * 获取最大位数
         * @param x
         * @return
         */
        public static int getMaxBit(int[] array) {
            int max = Integer.MIN_VALUE;
            for(int element : array) {
                int len = (element+"").length();
                if(len > max)
                    max = len;
            }
            return max;
        }
        
        /**
         * 获取x的第n位，如果没有则为0.
         * @param x
         * @param n
         * @return
         */
        public static int getNBit(int x, int n) {
            String sx = x + "";
            if(sx.length() < n)
                return 0;
            else
                return sx.charAt(sx.length()-n) - '0';
        }
    }

**12.计数排序：**  
计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。

计数排序对输入的数据有附加的限制条件：

(1)输入的线性表的元素属于有限偏序集S；

(2)设输入的线性表的长度为n，|S|=k（表示集合S中元素的总数目为k），则k=O(n)。 在这两个条件下，计数排序的复杂性为O(n)。

计数排序的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。例如，如果输入序列中只有17个元素的值小于x的值，则x可以直接存放在输出序列的第18个位置上。当然，如果有多个元素具有相同的值时，我们不能将这些元素放在输出序列的同一个位置上，因此，上述方案还要作适当的修改。

计数排序CountSort代码：

package sort;
    
    import java.util.Arrays;
    
    /** 
     * @author  WuPing
     * @date 2016年4月10日 上午10:57:32 
     * @version 1.0 
     * @parameter  
     * @since  
     * @return  
     */
    public class CountSort {
    	public static void countSort(int[] array) {  
            if(array != null && array.length != 0) {
            	int max = max(array);  
                int[] count = new int[max+1];  
                Arrays.fill(count, 0);  
                for(int i=0; i<array.length; i++) {  
                    count[array[i]] ++;  
                }  
                int k = 0;  
                for(int i=0; i<=max; i++) {  
                    for(int j=0; j<count[i]; j++) {  
                    	array[k++] = i;  
                    }  
                }     
            }
        }  
          
        public static int max(int[] array) {  
            int max = Integer.MIN_VALUE;  
            for(int element : array) {  
                if(element > max)  
                    max = element;  
            }   
            return max;  
        }  
    }

**13.桶排序：**桶排序算是计数排序的一种改进和推广。  
 桶排序 (Bucket sort) 或所谓的箱排序，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间([Θ][Link 1](n))。但桶排序并不是 比较排序，它不受到 O(n log n) [下限][Link 2]的影响。桶排序是稳定的。

桶排序分析： 桶排序利用函数的映射关系，减少了几乎所有的比较工作。实际上，桶排序的f(k)值的计算，其作用就相当于快排中划分，希尔排序中的子序列，归并排序中的子问题，已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做先进的比较排序即可。

对N个关键字进行桶排序的时间复杂度分为两个部分：

(1) 循环计算每个关键字的桶映射函数，这个时间复杂度是O(N)。

(2) 利用先进的比较排序算法对每个桶内的所有数据进行排序，其时间复杂度为 ∑ O(Ni\*logNi) 。其中Ni 为第i个桶的数据量。

很显然，第(2)部分是桶排序性能好坏的决定因素。尽量减少桶内数据的数量是提高效率的唯一办法(因为基于比较排序的最好平均时间复杂度只能达到O(N\*logN)了)。因此，我们需要尽量做到下面两点：

(1) 映射函数f(k)能够将N个数据平均的分配到M个桶中，这样每个桶就有\[N/M\]个数据量。

(2) 尽量的增大桶的数量。极限情况下每个桶只能得到一个数据，这样就完全避开了桶内数据的“比较”排序操作。当然，做到这一点很不容易，数据量巨大的情况下，f(k)函数会使得桶集合的数量巨大，空间浪费严重。这就是一个时间代价和空间代价的权衡问题了。

桶排序BucketSort代码：

package sort;
    
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.LinkedList;
    import java.util.List;
    
    /** 
     * @author  WuPing
     * @date 2016年4月10日 下午3:20:43 
     * @version 1.0 
     * @parameter  
     * @since  
     * @return  
     */
    public class BucketSort {
    	
    	static int BucketNums = 10;    //这里默认为10，规定待排数[0,100) 
    	
    	public static void bucketSort(int[] array) {  
            if(array != null && array.length != 0){  
                List<List<Integer>> buckets = new ArrayList<List<Integer>>();  //桶的索引  
                  
                for(int i=0; i<10; i++) {  
                    buckets.add(new LinkedList<Integer>());  //用链表比较合适  
                }  
                  
                //划分桶  
                for(int i=0; i<array.length; i++) {  
                    buckets.get(f(array[i])).add(array[i]);  
                }  
                  
                //对每个桶进行排序  
                for(int i=0; i<buckets.size(); i++) {  
                    if(!buckets.get(i).isEmpty()) {  
                        Collections.sort(buckets.get(i));  //对每个桶进行快排  
                    }  
                }  
                  
                //还原排好序的数组  
                int k = 0;  
                for(List<Integer> bucket : buckets) {  
                    for(int element : bucket) {  
                        array[k++] = element;  
                    }  
                }  
            }
        }  
          
        /** 
         * 映射函数 
         * @param x 
         * @return 
         */  
        public static int f(int x) {  
            return x / BucketNums;  
        }  
    }

测试排序效果，我使用随机函数生成100个范围在0-100的随机数，用上述排序算法分别对生成的随机数组进行排序，比较排序时间。

package sort;
    import java.util.Random;
    /** 
     * @author  WuPing
     * @date 2016年4月2日 下午10:27:00 
     * @version 1.0 
     * @parameter  
     * @since  
     * @return  
     */
    public class Test {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int N = 100;
    		int[] arrayA = new int[N];
    		int[] arrayB = new int[N];
    	   	for (int i = 0; i < N; i++) {
    	         Random radomNum = new Random();
    	         arrayB[i] = radomNum.nextInt(90);
    	   	}
    	   	
    	   	System.out.println("冒泡排序前的整形数组：");
    	   	for (int i = 0; i < N; i++) {
    	   		arrayA[i]=arrayB[i];
    	   		System.out.print(arrayA[i] + " ");
    	   	}
    	   	System.out.println();
    	   	long bubbleSortStartTime=System.nanoTime();   //获取开始时间
    	   	BubbleSort.bubbleSort(arrayA);
            long bubbleSortEndTime=System.nanoTime();     //获取结束时间
            System.out.println("冒泡排序执行时间： "+(bubbleSortEndTime-bubbleSortStartTime)+"ns");
    	   	System.out.println("冒泡排序后的整形数组：");
    	   	for (int i = 0; i < arrayA.length; i++) {
    	   		System.out.print(arrayA[i] + " ");
    	   	}
    	   	System.out.println();
    	   	
    	   	System.out.println();
    	    System.out.println("选择排序前的整形数组：");
    	   	for (int i = 0; i < N; i++) {
    	   		arrayA[i]=arrayB[i];
    	   		System.out.print(arrayA[i] + " ");
    	   	}
    	   	System.out.println();
    	   	long selectSortStartTime=System.nanoTime();   //获取开始时间
    	    SelectSort.selectSort(arrayA);
            long selectSortEndTime=System.nanoTime();     //获取结束时间
            System.out.println("选择排序执行时间： "+(selectSortEndTime-selectSortStartTime)+"ns");
    	   	System.out.println("选择排序后的整形数组：");
    	   	for (int i = 0; i < arrayA.length; i++) {
    	        System.out.print(arrayA[i] + " ");
    	   	}
    	   	System.out.println();
    	   	
    	   	System.out.println();
    	    System.out.println("插入排序前的整形数组：");
    	   	for (int i = 0; i < N; i++) {
    	   		arrayA[i]=arrayB[i];
    	   		System.out.print(arrayA[i] + " ");
    	   	}
    	   	System.out.println();
    	   	long insertSortStartTime=System.nanoTime();   //获取开始时间
    	    InsertSort.insertSort(arrayA);
            long insertSortEndTime=System.nanoTime();     //获取结束时间
            System.out.println("插入排序执行时间： "+(insertSortEndTime-insertSortStartTime)+"ns");
    	   	System.out.println("插入排序后的整形数组：");
    	   	for (int i = 0; i < arrayA.length; i++) {
    	   		System.out.print(arrayA[i] + " ");
    	   	}
    	   	System.out.println();
    	   	
    	   	System.out.println();
    	    System.out.println("快速排序前的整形数组：");
    	   	for (int i = 0; i < N; i++) {
    	   		arrayA[i]=arrayB[i];
    	   		System.out.print(arrayA[i] + " ");
    	   	}
    	   	System.out.println();
    	   	long quickSortStartTime=System.nanoTime();   //获取开始时间
    	   	QuickSort.sort(arrayA);
            long quickSortEndTime=System.nanoTime();     //获取结束时间
            System.out.println("快速排序执行时间： "+(quickSortEndTime-quickSortStartTime)+"ns");
    	   	System.out.println("快速排序后的整形数组：");
    	   	for (int i = 0; i < arrayA.length; i++) {
    	        System.out.print(arrayA[i] + " ");
    	   	}
    	   	System.out.println();
    	   	
    	   	System.out.println();
    	    System.out.println("堆排序前的整形数组：");
    	   	for (int i = 0; i < N; i++) {
    	   		arrayA[i]=arrayB[i];
    	   		System.out.print(arrayA[i] + " ");
    	   	}
    	   	System.out.println();
    	   	long heapSortStartTime=System.nanoTime();   //获取开始时间
    	   	HeapSort.heapSort(arrayA);
            long heapSortEndTime=System.nanoTime();     //获取结束时间
            System.out.println("堆排序执行时间： "+(heapSortEndTime-heapSortStartTime)+"ns");
    	   	System.out.println("堆排序后的整形数组：");
    	   	for (int i = 0; i < arrayA.length; i++) {
    	        System.out.print(arrayA[i] + " ");
    	   	}
    	   	System.out.println();
    	   	
    		System.out.println();
    	    System.out.println("希尔排序前的整形数组：");
    	   	for (int i = 0; i < N; i++) {
    	   		arrayA[i]=arrayB[i];
    	   		System.out.print(arrayA[i] + " ");
    	   	}
    	   	System.out.println();
    	   	long shellSortStartTime=System.nanoTime();   //获取开始时间
    	   	ShellSort.shellSort(arrayA);
            long shellSortEndTime=System.nanoTime();     //获取结束时间
            System.out.println("希尔排序执行时间： "+(shellSortEndTime-shellSortStartTime)+"ns");
    	   	System.out.println("希尔排序后的整形数组：");
    	   	for (int i = 0; i < arrayA.length; i++) {
    	        System.out.print(arrayA[i] + " ");
    	   	}
    	   	System.out.println();
    	   	
    	   	System.out.println();
    	    System.out.println("归并排序前的整形数组：");
    	   	for (int i = 0; i < N; i++) {
    	   		arrayA[i]=arrayB[i];
    	   		System.out.print(arrayA[i] + " ");
    	   	}
    	   	System.out.println();
    	   	long mergeSortStartTime=System.nanoTime();   //获取开始时间
    	   	MergeSort.mergeSort(arrayA);
            long mergeSortEndTime=System.nanoTime();     //获取结束时间
            System.out.println("归并排序执行时间： "+(mergeSortEndTime-mergeSortStartTime)+"ns");
    	   	System.out.println("归并排序后的整形数组：");
    	   	for (int i = 0; i < arrayA.length; i++) {
    	        System.out.print(arrayA[i] + " ");
    	   	}
    	   	System.out.println();
    	   	
    	   	System.out.println();
    	    System.out.println("计数排序前的整形数组：");
    	   	for (int i = 0; i < N; i++) {
    	   		arrayA[i]=arrayB[i];
    	   		System.out.print(arrayA[i] + " ");
    	   	}
    	   	System.out.println();
    	   	long countSortStartTime=System.nanoTime();   //获取开始时间
    	   	CountSort.countSort(arrayA);
            long countSortEndTime=System.nanoTime();     //获取结束时间
            System.out.println("计数排序执行时间： "+(countSortEndTime-countSortStartTime)+"ns");
    	   	System.out.println("计数排序后的整形数组：");
    	   	for (int i = 0; i < arrayA.length; i++) {
    	        System.out.print(arrayA[i] + " ");
    	   	}
    	   	System.out.println();
    	   	
    	   	System.out.println();
    	    System.out.println("桶排序前的整形数组：");
    	   	for (int i = 0; i < N; i++) {
    	   		arrayA[i]=arrayB[i];
    	   		System.out.print(arrayA[i] + " ");
    	   	}
    	   	System.out.println();
    	   	long bucketSortStartTime=System.nanoTime();   //获取开始时间
    	   	BucketSort.bucketSort(arrayA);
            long bucketSortEndTime=System.nanoTime();     //获取结束时间
            System.out.println("桶排序执行时间： "+(bucketSortEndTime-bucketSortStartTime)+"ns");
    	   	System.out.println("桶排序后的整形数组：");
    	   	for (int i = 0; i < arrayA.length; i++) {
    	        System.out.print(arrayA[i] + " ");
    	   	}
    	   	System.out.println();
    	   	
    	   	System.out.println();
    	    System.out.println("基数排序前的整形数组：");
    	   	for (int i = 0; i < N; i++) {
    	   		arrayA[i]=arrayB[i];
    	   		System.out.print(arrayA[i] + " ");
    	   	}
    	   	System.out.println();
    	   	long radixSortStartTime=System.nanoTime();   //获取开始时间
    	   	RadixSort.radixSort(arrayA);
            long radixSortEndTime=System.nanoTime();     //获取结束时间
            System.out.println("基数排序执行时间： "+(radixSortEndTime-radixSortStartTime)+"ns");
    	   	System.out.println("基数排序后的整形数组：");
    	   	for (int i = 0; i < arrayA.length; i++) {
    	        System.out.print(arrayA[i] + " ");
    	   	}
    	   	System.out.println();
    	   	
    	   	System.out.println();
    	    System.out.println("折半插入排序前的整形数组：");
    	   	for (int i = 0; i < N; i++) {
    	   		arrayA[i]=arrayB[i];
    	   		System.out.print(arrayA[i] + " ");
    	   	}
    	   	System.out.println();
    	   	long binaiSortStartTime=System.nanoTime();   //获取开始时间
    	   	BinaiSort.binaiSort(arrayA);
            long binaiSortEndTime=System.nanoTime();     //获取结束时间
            System.out.println("折半插入排序执行时间： "+(binaiSortEndTime-binaiSortStartTime)+"ns");
    	   	System.out.println("折半插入排序后的整形数组：");
    	   	for (int i = 0; i < arrayA.length; i++) {
    	        System.out.print(arrayA[i] + " ");
    	   	}
    	   	System.out.println();
    	   	
    		System.out.println();
    	    System.out.println("2路插入排序前的整形数组：");
    	   	for (int i = 0; i < N; i++) {
    	   		arrayA[i]=arrayB[i];
    	   		System.out.print(arrayA[i] + " ");
    	   	}
    	   	System.out.println();
    	   	long twoSortStartTime=System.nanoTime();   //获取开始时间
    	   	TwoSort.twoSort(arrayA);
            long twoSortEndTime=System.nanoTime();     //获取结束时间
            System.out.println("2路插入排序执行时间： "+(twoSortEndTime-twoSortStartTime)+"ns");
    	   	System.out.println("2路插入排序后的整形数组：");
    	   	for (int i = 0; i < arrayA.length; i++) {
    	        System.out.print(arrayA[i] + " ");
    	   	}
    	   	System.out.println();
    	   	
    	   	System.out.println();
    	    System.out.println("树形选择排序前的整形数组：");
    	   	for (int i = 0; i < N; i++) {
    	   		arrayA[i]=arrayB[i];
    	   		System.out.print(arrayA[i] + " ");
    	   	}
    	   	System.out.println();
    	   	long treeSelectSortStartTime=System.nanoTime();   //获取开始时间
    	   	TreeSelectSort.treeSelectSort(arrayA);
            long treeSelectSortEndTime=System.nanoTime();     //获取结束时间
            System.out.println("树形选择排序执行时间： "+(treeSelectSortEndTime-treeSelectSortStartTime)+"ns");
    	   	System.out.println("树形选择排序后的整形数组：");
    	   	for (int i = 0; i < arrayA.length; i++) {
    	        System.out.print(arrayA[i] + " ");
    	   	}
    	   	System.out.println();
    	}
    
    }

测试结果截图：![SouthEast 3][]![SouthEast 4][]![SouthEast 5][]![SouthEast 6][]

总结：

各种内部排序算法的比较：如下图

![SouthEast 7][]

❶ 从平均时间来看，快速排序是效率最高的，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后者相比较的结果是，在n较大时归并排序使用时间较少，但使用辅助空间较多。

❷ 上面说的简单排序包括除希尔排序之外的所有冒泡排序、插入排序、简单选择排序。其中直接插入排序最简单，但序列基本有序或者n较小时，直接插入排序是好的方法，因此常将它和其他的排序方法，如快速排序、归并排序等结合在一起使用。

❸ 基数排序的时间复杂度也可以写成O(d\*n)。因此它最使用于n值很大而关键字较小的的序列。若关键字也很大，而序列中大多数记录的最高关键字均不同，则亦可先按最高关键字不同，将序列分成若干小的子序列，而后进行直接插入排序。

❹ 从方法的稳定性来比较，基数排序是稳定的内排方法，所有时间复杂度为O(n^2)的简单排序也是稳定的。但是快速排序、堆排序、希尔排序等时间性能较好的排序方法都是不稳定的。稳定性需要根据具体需求选择。

❺ 上面的算法实现大多数是使用线性存储结构，像插入排序这种算法用链表实现更好，省去了移动元素的时间。具体的存储结构在具体的实现版本中也是不同的。

牛顿说过：如果说我所看的比笛卡尔更远一点，那是因为站在巨人肩上的缘故。

参考文章：

# ⑴ 面试中的10大排序算法总结：[http://www.phpxs.com/post/4791][http_www.phpxs.com_post_4791] #

⑵ 树形排序：[http://zhouyunan2010.iteye.com/blog/1217462][http_zhouyunan2010.iteye.com_blog_1217462]

⑶ 二路插入排序：[ http://blog.csdn.net/zhangxiangdavaid/article/details/27958143][http_blog.csdn.net_zhangxiangdavaid_article_details_27958143]

[SouthEast]: /images/20220724/d5cce8da1bb749b5a44e25f08b67c397.png
[SouthEast 1]: /images/20220724/3fa5ef536b794a149c07b28d7ec34c73.png
[SouthEast 2]: /images/20220724/ca56201ee5314a3cb8f28f240324c89f.png
[Link 1]: http://baike.baidu.com/view/1405573.htm
[Link 2]: http://baike.baidu.com/view/1335512.htm
[SouthEast 3]: https://img-blog.csdn.net/20160412161727317?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 4]: https://img-blog.csdn.net/20160412161734426?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 5]: https://img-blog.csdn.net/20160412161740710?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 6]: /images/20220724/554b9142280648d894619864895a24b4.png
[SouthEast 7]: /images/20220724/b753833b91ee407d95f8370221551ad9.png
[http_www.phpxs.com_post_4791]: http://www.phpxs.com/post/4791
[http_zhouyunan2010.iteye.com_blog_1217462]: http://zhouyunan2010.iteye.com/blog/1217462
[http_blog.csdn.net_zhangxiangdavaid_article_details_27958143]: http://blog.csdn.net/zhangxiangdavaid/article/details/27958143