九、基数排序

原理

基数排序（Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

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

效率

基数排序的时间复杂度是O(k·n)，其中n是排序元素个数，k是数字位数。注意这不是说这个时间复杂度一定优于O(n·log(n))，k的大小取决于数字位的选择和待排序数据所属数据类型的全集的大小；k决定了进行多少轮处理，而n是每轮处理的操作数目。

基数排序基本操作的代价较小，k一般不大于logn，所以基数排序一般要快过基于比较的排序，比如快速排序。

最差空间复杂度是O(k·n)

Java实现

这里写图片描述

现在有数组：278，109，63,930,589,184,505,269,8,83　。根据各位数将数组划分为10个链表(当然其中的某些链表可能不含有元素)

第一次分配：

0:930
1:
2:
3:63,83
4:184
5:505
6：
7:
8:278,8
9:109,589,269

第一次收集后的数组：

930,63,83,184,505，278,8,109,589,269

第二次分配：

0:505,8,109
1:
2:
3:930
4:
5:
6：63,269
7:278
8:83,184，589
9:

第二次收集后的数组：

505,8,109，930，63,269，278，83,184，589

第三次分配：

0:8,63,83
1:109,184
2:278,269
3:
4:
5:505,589
6:
7:
8:
9:930

最后得到序列：

8,63,83,109,184，269,278,505,589,930

基数排序其实是利用多关键字先达到局部有序，再调整达到全局有序。

代码实现：

public class Test {
    public static void main(String[] args) {

        int[] array = {278,109,63,930,589,184,505,269,8,83};  
        radixSort(array);  
        for(double a : array){
            System.out.println(a);
        }
    }
public static void radixSort(int[] array){

        //------------------------------------------确定排序的趟数----------------------------------
        int max=array[0];
        for(int i=1;i<array.length;i++){
            if(array[i]>max){
                max=array[i];
            }
        }
        int time=0;
        while(max>0){
            max/=10;
            time++;
        }
        //----------------------------------------初始化10个链表用户分配时暂存-------------------------------
        List<List<Integer>> list=new ArrayList<List<Integer>>();
        for(int i=0;i<10;i++){
            List<Integer> item=new ArrayList<Integer>();
            list.add(item);
        }

        //-----------------------------------------进行time次分配和收集-------------------------------------
      for(int i=0;i<time;i++){
            //分配元素;
            for(int j=0;j<array.length;j++){
                int index = array[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i);
                list.get(index).add(array[j]);
            }
            //收集元素;
            int count=0;
            for(int k=0;k<10;k++){
                if(list.get(k).size()>0){
                    for(int a : list.get(k)){
                        array[count]=a;
                        count++;
                    }
                    //清除数据，以便下次收集
                    list.get(k).clear();
                }
            }
        }
    }
}

运行结果：

这里写图片描述

十、插入排序

概述

将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，是稳定的排序方法。

插入排序又分为　直接插入排序　和折半插入排序。

直接插入排序

把待排序的纪录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的纪录插入完为止，得到一个新的有序序列。

Java实现

    public static void insertSort(int a[]){  
        int j;       //当前要插入值的位置  
        int preJ;     //依次指向j前的位置  
        int key;       //后移时来暂存要插入的值

        //从数组的第二个位置开始遍历值  
        for(j=1;j<a.length;j++){  
            key=a[j];  
            preJ=j-1;  
            //a[preJ]比当前值大时，a[preJ]后移一位  
            while(preJ>=0 && a[preJ]>key){  
                a[preJ+1]=a[preJ]; //将a[preJ]值后移   

     //这里注意:  a[preJ+1]=a[j]=key,把插入值已经存在了 key中
    //等于说, 留出来一个空白位置来实现依次后移（不会造成数据丢失问题）

                preJ--;         //preJ前移  
            }
            //找到要插入的位置或已遍历完成（(preJ=0）
            a[preJ+1]=key;    //将当前值插入 空白位置
        }  
    }

备注很清楚，我就不多说了．．．．

效率分析

空间复杂度O(1)

平均时间复杂度O(n^2)

最差情况：反序，需要移动n*(n-1)/2个元素，运行时间为O(n^2)。

最好情况：正序，不需要移动元素，运行时间为O(n)．

折半插入排序

直接插入排序中要把插入元素与已有序序列元素依次进行比较，效率非常低。

折半插入排序,使用使用折半查找的方式寻找插入点的位置, 可以减少比较的次数,但移动的次数不变, 时间复杂度和空间复杂度和直接插入排序一样，在元素较多的情况下能提高查找性能。

Java实现

private static void binaryInsertSort(int[] a)  
    {  
        //从数组的第二个位置开始遍历值    
        for(int i = 1; i < a.length; i++)  {  
            int key = a[i];           //暂存要插入的值    
            int pre = 0;              //有序序列开始和结尾下标申明
            int last = i - 1;       
        // 折半查找出插入位置 a[pre]
            while(pre <= last)  {  
                int mid = (pre + last) / 2;                
                if(key < a[mid])  {  
                    last = mid - 1;  
                } else {  
                    pre = mid + 1;  
                }  
            }  
     //a[i]已经取出来存放在key中，把下标从pre + 1到 i-1的元素依次后移
            for(int j = i; j >= pre + 1; j--)  {  
                a[j] = a[j - 1];  
            }  
            //把值插入空白位置
            a[pre] = key;            
        }  
    }

直接插入排序是，比较一个后移一个；
折半插入排序是，先找到位置，然后一起移动；

十一、补充

1. 快排的partition函数

作用：给定一个数组arr[]和数组中任意一个元素a，重排数组使得a左边都小于它，右边都不小于它。

// A[]为数组，start、end分别为数组第一个元素和最后一个元素的索引
 // povitIndex为数组中任意选中的数的索引
static int partition(int A[], int start, int end, int pivotIndex){
    int i = start, j = end, pivot = A[pivotIndex];
    swap<int>(A[end], A[pivotIndex]);
    while(i < j){
        while(i < j && A[i] <= pivot) ++i;
        while(i < j && A[j] >= pivot) --j;
        if(i < j) swap<int>(A[i], A[j]);
    }
    swap<int>(A[end], A[i]);
    return i;
}

2. 冒泡排序的改进

思路：

①、加一个标志位，当某一趟冒泡排序没有元素交换时，则冒泡结束，元素已经有序，可以有效的减少冒泡次数。

  /** 
     * 引入标志位，默认为true 
     * 如果前后数据进行了交换，则为true，否则为false。如果没有数据交换，则排序完成。 
     */  
    public static int[] bubbleSort(int[] arr){  
        boolean flag = true;  
        int n = arr.length;  
        while(flag){  
            flag = false;  
            for(int j=0;j<n-1;j++){  
                if(arr[j] >arr[j+1]){  
                    //数据交换  
                    int temp = arr[j];  
                    arr[j] = arr[j+1];  
                    arr[j+1] = temp;  
                    //设置标志位  
                    flag = true;  
                }  
            }  
            n--;  
        }  
        return arr;  
    }