大话数据结构——排序

本文在阅读大话数据结构这本书的基础上，结合java语言的特点，来理解排序。

排序方法	平均情况	最好情况	最坏情况	辅助空间	稳定性
冒泡排序	O(n^2)	O(n)	O(n^2)	O(1)	稳定
简单选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	稳定
直接插入排序	O(n^2)	O(n)	O(n^2)	O(1)	稳定
希尔排序	O(nlogn)~O(n^2)	O(n^1.3)	O(n^2)	O(1)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定
快速排序	O(nlogn)	O(nlogn)	O(n^2)	O(logn)~O(n)	不稳定

排序的基本概念

假设含有n个记录的序列为{r1,r2,……,rn}，其相应的关键字分别为{k1,k2,……,kn}，需确定1，2，……，n的一种排列p1,p2,……,pn，使其相应的关键字满足kp1≤kp2≤……≤kpn（非递减或非递增）关系，即使得序列成为一个按关键字有序的序列{rp1,rp2,……,rpn}，这样的操作就称为排序。假设ki=kj（1≤i≤n,1≤j≤n,i≠j），且在排序前的序列中ri领先于rj（即i<j）。如果排序后ri仍领先于rj，则称所用的排序方法是稳定的；反之，若可能使得排序后的序列中rj领先ri，则称所用的排序方法是不稳定的。

内排序与外排序：根据在排序过程中待排序的记录是否全部被放置在内存中。内排序是在排序整个过程中，待排序的所有记录全部被放置在内存中。外排序是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行。

对于内排序来说，排序算法的性能主要是受三个方面影响：时间性能；辅助空间；算法的复杂性。

排序的结构图如下：

交换排序

冒泡排序

包含传统冒泡和优化冒泡两种方式实现

public class Sort {
    public void swap(int[] array,int i,int j){
        if(i<array.length&&j<array.length){
            int data=array[i];
            array[i]=array[j];
            array[j]=data;
        }
    }
}
/**
 * 冒泡排序
 */
public class BubbleSort extends Sort{
    /**
     * 冒泡排序
     */
    public void bubbleSort(int[] array){
        if(array.length<2){
            return;
        }
        int i,j;
        for(i=0;i<array.length-1;i++){
            for(j=array.length-1;j>i;j--){
                if(array[j]<array[j-1]){
                    swap(array,j,j-1);
                }
            }
        }
    }
    /**
     * 优化的冒泡排序
     */
    public void bubbleSort2(int[] array){
        if(array.length<2){
            return;
        }
        int i,j;
        boolean flag=true;
        for(i=0 ; i<array.length-1 && flag ; i++){
            flag=false;
            for(j=array.length-1;j>i;j--){
                if(array[j]<array[j-1]){
                    swap(array,j,j-1);
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] array={9,1,5,8,3,7,4,6,2};
        System.out.println(Arrays.toString(array));
        BubbleSort bubbleSort=new BubbleSort();
        bubbleSort.bubbleSort(array);
        System.out.println(Arrays.toString(array));
        int[] array2={2,1,3,4,5,6,7,8,9};
        System.out.println(Arrays.toString(array2));
        bubbleSort.bubbleSort2(array2);
        System.out.println(Arrays.toString(array2));
    }
}

快速排序

包含递归和尾递归优化实现

/**
 * 快速排序
 */
public class QuickSort {
    /**
     * 对数组进行快速排序
     */
    public void quickSort(int[] array){
        if(array.length>1){
            qSort(array,0,array.length-1);
        }
    }
    /**
     * 利用递归对数组子序列进行快速排序
     */
    private void qSort(int[] array,int left,int right){
        if(left<right){
            int pivot;
            pivot=partition(array,left,right);
            qSort(array,left,pivot);
            qSort(array,pivot+1,right);
        }
    }
    /**
     * 递归优化对数组进行快速排序
     */
    public void quickSort2(int[] array){
        if(array.length>1){
            qSort2(array,0,array.length-1);
        }
    }
    /**
     * 尾递归优化对数组子序列进行快速排序
     */
    private void qSort2(int[] array,int left,int right){
        while(left<right){
            int pivot;
            pivot=partition(array,left,right);
            qSort2(array,left,pivot);
            left=pivot+1;
        }
    }
    /**
     * 分区（将较小的数分至左侧，较大的数分至右侧）
     */
    private int partition(int[] array,int left,int right){
        // TODO（可优化） 将枢轴（支点）放至数组第一个元素
        int data=array[left];
        while(left<right){
            while(left<right && array[right]>=data){
                right--;
            }
            array[left]=array[right];//将右侧较小的数替换至左侧
            while(left<right && array[left]<=data){
                left++;
            }
            array[right]=array[left];//将左侧较大的数替换至右侧
        }
        array[left]=data;//将枢轴替换至left位置
        return left;
    }

    public static void main(String[] args) {
        int[] array={9,1,5,8,3,7,4,6,2};
        System.out.println(Arrays.toString(array));
        QuickSort quickSort=new QuickSort();
        quickSort.quickSort(array);
        System.out.println(Arrays.toString(array));
        int[] array2={9,1,5,8,3,7,4,6,2};
        System.out.println(Arrays.toString(array2));
        quickSort.quickSort2(array2);
        System.out.println(Arrays.toString(array2));
    }
}

插入排序

直接插入排序

/**
 * 直接插入排序
 */
public class StraightInsertionSort {
    public void insertSort(int[] array){
        if(array.length>1){
            int i,j;
            for(i=1;i<array.length;i++){
                if(array[i-1]>array[i]){
                    int data=array[i];
                    for(j=i;j>0 && array[j-1]>data;j--){
                        array[j]=array[j-1];
                    }
                    array[j]=data;
                }

            }
        }
    }

    public static void main(String[] args) {
        int[] array={9,1,5,8,3,7,4,6,2};
        System.out.println(Arrays.toString(array));
        StraightInsertionSort straightInsertionSort=new StraightInsertionSort();
        straightInsertionSort.insertSort(array);
        System.out.println(Arrays.toString(array));
    }
}

希尔排序

/**
 * 希尔排序
 */
public class ShellSort extends Sort{
    public void shellSort(int[] array){
        if(array.length>1){
            int increment=array.length/2;
            while(increment>=1){
                for(int i=0;i<array.length;i++){
                    for(int j=i;j<array.length-increment;j +=increment){
                        if(array[j]>array[j+increment]){
                            swap(array,j,j+increment);
                        }
                    }
                }
                increment=increment/2;
            }
        }
    }

    public static void main(String[] args) {
        int[] array={9,1,5,8,3,7,4,6,2};
        System.out.println(Arrays.toString(array));
        ShellSort shellSort=new ShellSort();
        shellSort.shellSort(array);
        System.out.println(Arrays.toString(array));
    }
}

选择排序

简单选择排序

/**
 * 简单选择排序
 */
public class SimpleSelectionSort extends Sort{
    public void selectSort(int[] array){
        if(array.length>1){
            int i,j,min;
            for(i=0;i<array.length-1;i++){
                min=i;
                for(j=min+1;j<array.length;j++){
                    if(array[min]>array[j]){
                        min=j;
                    }
                }
                if(min!=i){
                    swap(array,i,min);
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] array={9,1,5,8,3,7,4,6,2};
        System.out.println(Arrays.toString(array));
        SimpleSelectionSort simpleSelectionSort=new SimpleSelectionSort();
        simpleSelectionSort.selectSort(array);
        System.out.println(Arrays.toString(array));
    }
}

堆排序

/**
 * 堆排序
 */
public class HeapSort extends Sort {
    public void heapSort(int[] array){
        if(array.length>1){
            for(int i=array.length/2;i>=0;i--){
                heapAdjust(array,i,array.length);
            }
            for(int i=array.length-1;i>=1;i--){
                swap(array,0,i);
                heapAdjust(array,0,i);
            }
        }

    }
    public void heapAdjust(int[] array,int i,int length){
        int data=array[i];
        for(int j=2*i+1;j<=length-1;j=2*j+1){
            if(j<length-1 && array[j]<array[j+1]){
                j++;
            }
            if(data>=array[j]){
                break;
            }
            array[i]=array[j];
            i=j;
        }
        array[i]=data;
    }

    public static void main(String[] args) {
        int[] array={9,1,5,8,3,7,4,6,2};
        System.out.println(Arrays.toString(array));
        HeapSort heapSort=new HeapSort();
        heapSort.heapSort(array);
        System.out.println(Arrays.toString(array));
    }
}

归并排序

包含递归和非递归实现

/**
 * 归并排序
 */
public class MergingSort {
    /**
     * 递归实现归并排序
     */
    public void mergeSort(int[] array){
        if(array.length>1){
            mSort(array,0,array.length-1);
        }
    }
    /**
     * 数组拆分
     */
    private 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);
        }
    }
    /**
     * 数组归并
     */
    private void merge(int[] array , int left , int mid , int right){
        int[] num=new int[right-left+1];
        int i = left;
        int j = mid+1;
        int count=0;
        while(i<=mid && j<=right){
            if(array[i]>array[j]){
                num[count++]=array[j++];
            }else{
                num[count++]=array[i++];
            }
        }
        while(i<=mid){
            num[count++]=array[i++];
        }
        while(j<=right){
            num[count++]=array[j++];
        }
        count=0;
        while(left<=right){
            array[left++]=num[count++];
        }
    }

    /**
     * 非递归实现归并排序
     */
    public void mergeSort2(int[] array){
        if(array.length>1){
            int length=1;
            while(length<array.length){
                for(int i=0;i<array.length;i+=2*length){
                    if(i+2*length<array.length){
                        merge(array,i,i+length-1,i+2*length-1);
                    }else if(i+length<array.length){
                        merge(array,i,i+length-1,array.length-1);
                    }else{
                        merge(array,i,array.length-1,array.length-1);
                    }
                }
                length *=2;
            }
        }
    }

    public static void main(String[] args) {
        int[] array={9,1,5,8,3,7,4,6,2};
        System.out.println(Arrays.toString(array));
        MergingSort mergingSort=new MergingSort();
        mergingSort.mergeSort(array);
        System.out.println(Arrays.toString(array));
        int[] array2={9,1,5,8,3,7,4,6,2};
        System.out.println(Arrays.toString(array2));
        mergingSort.mergeSort2(array2);
        System.out.println(Arrays.toString(array2));
    }
}

基数排序

基于两种不同的排序顺序，我们将基数排序分为LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由数值的最右边（低位）开始，而MSD则相反，由数值的最左边（高位）开始。注意一点：LSD的基数排序适用于位数少的数列，如果位数多的话，使用MSD的效率会比较好。

http://www.cnblogs.com/Braveliu/archive/2013/01/21/2870201.html

代码实现（包含LSD和MSD两种实现方式）

/**
 * 基数排序
 */
public class RadixSort {
    /**
     * LSD实现基数排序
     */
    public void radixSortLSD(int [] array,int radix,int digit){
        if(array.length>1){
            int num[]=new int[array.length];
            int buckets[]=new int[radix];//定义桶的数量
            int rate=1;
            for(int i=0;i<=digit;i++){
                Arrays.fill(buckets,0);
                //将数组元素复制到临时数组num中
                System.arraycopy(array,0,num,0,array.length);
                /**
                 * 计算各个桶的容量
                 */
                for(int j=0;j<array.length;j++){
                    int subKey=(array[j]/rate)%radix;
                    buckets[subKey]++;
                }
                /**
                 * 计算桶内元素在数组中应该排序的位置
                 */
                for(int j=1;j<radix;j++){
                    buckets[j]=buckets[j]+buckets[j-1];
                }
                /**
                 * 对数组元素按照余数进行排序
                 */
                for(int k=array.length-1;k>=0;k--){
                    int subKey =(num[k]/rate)%radix;
                    array[--buckets[subKey]]=num[k];
                }
                rate*=radix;
            }
        }
    }
    /**
     * MSD实现基数排序
     */
    public void radixSortMSD(int [] array,int left,int right,int radix,int digit){
        if(right>left){
            int num[]=new int[right-left+1];
            int buckets[]=new int[radix];//定义桶的数量
            int rate=(int)Math.pow(radix,digit-1);
            Arrays.fill(buckets,0);
            //将数组元素复制到临时数组num中
            System.arraycopy(array,left,num,0,right-left+1);
            /**
             * 计算各个桶的容量
             */
            for(int j=left;j<=right;j++){
                int subKey=(array[j]/rate)%radix;
                buckets[subKey]++;
            }
            /**
             * 计算桶内元素在数组中应该排序的位置
             */
            for(int j=1;j<radix;j++){
                buckets[j]=buckets[j]+buckets[j-1];
            }
            /**
             * 对数组元素按照商的余数进行排序
             */
            for(int k=num.length-1;k>=0;k--){
                int subKey =(num[k]/rate)%radix;
                array[left+(--buckets[subKey])]=num[k];
            }
            if(digit>0){
                int subKey;
                radixSortMSD(array,left,left+buckets[0]-1,radix,digit-1);
                for(subKey=0;subKey<radix-1;subKey++){
                    radixSortMSD(array,left+buckets[subKey],left+buckets[subKey+1]-1,radix,digit-1);
                }
                radixSortMSD(array,left+buckets[subKey],right,radix,digit-1);
            }
        }
    }

    public static void main(String[] args) {
        int[] array={20, 80, 90, 589, 998, 965, 852, 123, 456, 789};
        System.out.println(Arrays.toString(array));
        RadixSort radixSort=new RadixSort();
        radixSort.radixSortLSD(array,10,3);
        System.out.println(Arrays.toString(array));
        int[] array2={200, 1, 3, 42, 9, 64, 7, 81, 5, 10, 52, 61};
        System.out.println(Arrays.toString(array2));
        radixSort.radixSortMSD(array2,0,array2.length-1,10,3);
        System.out.println(Arrays.toString(array2));
    }

}