Java实现各种内部排序算法

数据结构中常见的内部排序算法：

　　插入排序：直接插入排序、折半插入排序、希尔排序

　　交换排序：冒泡排序、快速排序

　　选择排序：简单选择排序、堆排序

　　归并排序、基数排序、计数排序

直接插入排序：

　　思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中，直到全部记录插入完成。

　　性能：时间复杂度：最好o(n)：有序，最坏o(n^2)：逆序,平均o(n^2)；空间复杂度o(1)；稳定

　　public int[] straightInsertSort(int array[]){
        int temp;
        for(int i=1; i<array.length; i++){ //依次对1到array.length-1个元素进行处理  
            temp = array[i];
            for(int j=0; j<i; j++){  //已排好序的0到i-1个元素
                if(temp < array[j]){  //插入位置j
                    for(int k=i-1;k>=j;k--){  //将j到i-1个元素向后移一个位置
                        array[k+1]=array[k];  //此时array[i]为已排好序的子数组中的最大值
                    }
                    array[j] = temp;  //将第i个元素插入到位置j上
                    break;
                }
            }
        }
        return array;
    }

折半插入排序：

　　思想：利用折半查找的方法找出元素的待插入位置，然后再统一移动待插入位置之后的所有元素，最后将待插入元素插入到相应位置。

　　性能：平均情况下,比较次数o(nlogn)，移动次数o(n^2)

　　　　　时间复杂度:最好o(n)：有序，最坏o(n^2)：逆序,平均o(n^2)；空间复杂度o(1)；稳定

    public int[] binaryInsertSort(int[] array){
        int temp,low,high;
        for(int i=1; i<array.length; i++){
            temp = array[i];
            //从已排好序的0到i-1个元素中,折半查找出元素的待插入位置
            low = 0;
            high = i-1;
            while(low <= high){
                if(array[(low+high)/2] <= array[i]){
                    low = (low+high)/2 + 1;
                }else{
                    high = (low+high)/2 - 1;
                }
            }             
            //移动待插入位置low到i-1间的所有元素
            for(int j=i-1; j>=low; j-- ){
                array[j+1] = array[j];
            }
            array[low] = temp;
        }        
        return array;
    }

希尔排序：

　　思想：将排序表分割成若干个形如L[i,i+d,i+2d,...,i+kd]的“特殊”子表，分别进行直接插入排序，当整个表中元素已呈现“基本有序”时，再对全体记录进行一次直接插入排序（d=1时）。

　　　　　步长设置:d1=array.length/2;di=di/2，最后一个增量为1；

　　性能：时间复杂度：最坏o(n^2),平均o(n^1.3)，空间复杂度o(1)，不稳定

public int[] shellSort(int[] array){    
        for(int d=array.length/2; d>=1; d=d/2){ //用步长值来控制循环次数
            for(int i=d;i<array.length;i++){  
                int temp = array[i];
                if(temp < array[i-d]){  //将array[i]插入到有序增量子表中                    
                    int j;
                    for(j=i-d;j>=0 && temp<array[j];j-=d){
                        array[j+d]=array[j];  //记录后移，寻找插入位置
                    }
                    array[j+d] = temp;
                }
            }
        }
        return array;
    }

冒泡排序：

　　思想：对于待排序表，从前往后两两比较相邻元素的值，若为逆序，则交换，直到序列比较完成。如此，每次冒泡即可得到当前待排表中的最大元素，并已放置在相应的位置。

　　性能：时间复杂度：最好o(n)有序，最坏o(n^2)逆序,平均o(n^2)，空间复杂度o(1)，稳定

    public int[] bubbleSort(int[] array){
        boolean flag = false; //用来标记该序列是否已是有序
        for(int i=0;i<array.length-1;i++){ //做n-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 = true;  //有元素交换，则该序列初始状况不是有序的
                }
            }
            if(flag == false){  //本趟遍历后没有发生交换，说明表已经有序
                return array;
            }
        }
        return array;
    }

快速排序：

　　思想：基于分治的思想：在待排序表中任取一个元素pivot作为基准，通过一趟排序将待排序表划分为独立的两部分，使得一部分中所有元素小于等于pivot，另一部分中所有元素大于pivot，则pivot放在了其最终位置上，这个过程称为一趟快速排序。而后递归地对两个子表重复上述过程，直到每部分内只有一个元素或空为止。

　　性能： 空间复杂度：需要递归工作栈：最坏o(n)，平均o(logn)

　　　　　 时间复杂度：最坏:o(n^2)初始表基本有序或基本逆序，平均o(n*logn)

　　　　　 不稳定

　　public int[] quickSort(int[] array,int low,int high){
        if(low<high){  //递归跳出的条件
            int mid= partition(array, low, high); //划分，得到枢值所在的下表
            quickSort(array,low,mid-1);  //依次对两个子表进行递归排序
            quickSort(array,mid+1,high);
        }    
        return array;
    }
    //快速排序的划分函数
    public int partition(int[] array,int low, int high){
        int pivot = array[low];  //每次取数组中的第一个元素为基准
        while(low < high){  //跳出循环的条件
            while(low<high && array[high] > pivot){  //从右边开始找到第一个小于或等于pivot的值 
                high--;
            }
            while(low<high && array[low] < pivot){   //从左边开始找到第一个大于或等于pivot的值
                low++;
            }
            int temp = array[low];   //交换
            array[low] = array[high];
            array[high] = temp;
            if(low<high && array[low] == pivot && array[high] == pivot){  //特殊情况
                low++;
            }
        }
        return low;
    }

简单选择排序：

　　思想：假设排序表array[0,...,n-1]，第 i 趟排序即从array[0,...,n-1]中选择关键字最小的元素与array[i]交换，每一趟排序可以确定一个元素的最终位置，这样经过n-1趟派克就可以使整个序列有序。

　　性能：时间复杂度：o(n^2)，空间复杂度o(1)，不稳定

    public int[] simpleSelectSort(int[] array){
        for(int i=0;i<array.length -1;i++){  //一共进行n-1趟
            int min = i;  //记录最小元素位置
            for(int j=i+1;j<array.length;j++){ //在array[i，...，n-1]中选择最小的元素
                if(array[j] < array[min]){
                    min = j;   //更新最小元素的位置
                }
            }            
            int temp = array[i];  //将最小元素与第i个位置交换
            array[i] = array[min];
            array[min] = temp;
        }
        return array;
    }

堆排序：Java实现堆排序（大根堆）

归并排序：

　　思想：“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。假设待排序表含有n个记录，则可以看成是n个有序的子表，每个子表的长度为1，然后两两归并，得到（n/2）个长度为2或1的有序表；再两两归并，...，如此重复，直到合并成一个长度为n的有序表为止，这种排序方法称为2-路归并排序。

　　递归形式的2-路归并排序算法是基于分治的，其过程如下：

　　　　分解：将含有n个元素的待排序表分成各含有n/2个元素的子表，采用2-路归并排序算法对两个子表递归地进行排序；

　　　　合并：合并两个已排序的子表得到排序结果。

　　性能：空间复杂度：o(n)；时间复杂度:o(nlogn)；稳定

　　public int[] mergeSort(int[] array,int low, int high){
        if(low < high){  //递归结束的条件
            int mid = (low + high)/2;  //二路归并排序，从中间划分两个子序列【分解过程】
            mergeSort(array, low, mid); //对左侧子序列进行递归排序
            mergeSort(array, mid+1, high); //对右侧子序列进行递归排序
            merge(array,low,mid,high); //归并【合并过程】
        }
        return array;
    }
    
    //将前后相邻的两个有序表归并为一个有序表
    private void merge(int[] array,int low, int mid, int high){
        int[] tempArray = new int[array.length];  //辅助数组tempArray
        for(int i=low;i<=high;i++){ //将array数组中[low...high]的元素复制到辅助数组tempArray中
            tempArray[i] = array[i];
        }
        int i,j,k;
        for(i=low,j=mid+1,k=i;i<=mid && j<=high;k++){
            if(tempArray[i]>tempArray[j]){  //比较tempArray的左右两端中的元素
                array[k] = tempArray[j++];  //将较小值复制到array中
            }else{
                array[k] = tempArray[i++]; 
            }
        }
        while(i<=mid){    //若第一个表未检测完，复制
            array[k++] = tempArray[i++];
        }
        while(j<=high){      //若第二个表未检测完，复制
            array[k++] = tempArray[j++];
        }
    }

基数排序：

  基于计数排序实现： Java实现基于桶式排序思想和计数排序思想实现的基数排序

  基于队列辅助实现：

　　思想：基数排序不是基于比较进行排序的，而是采用多关键字排序思想，借助“分配”和“收集”两种操作对单逻辑关键字进行排序。

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

　　性能：空间复杂度：o(r)；时间复杂度：o(d(n+r))；稳定

　　　　　其中，r为基数，d为最大关键字的位数（决定了排序的趟数），n为待排序列表中元素的个数。

       //基于队列辅助实现的基数排序
 1     public int[] radixSort(int[] array){
        //找到待排序序列中的最大元素
        int max = array[0];
        for(int i=1; i<array.length;i++){
            if(array[i] > max){
                max = array[i];
            }
        }
        //确定最大元素的位数maxBits
        int maxBits = 0;
        while(max > 0){
            max = max/10;
            maxBits ++;
        }
        
        //建立10个队列
        Queue<Integer>[] queue = new LinkedList[10];
        for(int i=0; i<queue.length; i++){
            queue[i] = new LinkedList<Integer>();
        }
        
        //进行maxBits次分配和收集
        for(int i=0; i<maxBits;i++){
            //分配数组
            for(int j=0; j<array.length;j++){
                //得到元素的第maxBits位，然后将该元素插入到对应的位置
                queue[(array[j] % (int)Math.pow(10, i+1))/(int)Math.pow(10, i)].add(array[j]);
            }
            //元素计数器
            int count = 0;
            //收集队列元素
            for(int k=0;k<queue.length;k++){
                while(queue[k].size() > 0){
                    array[count++] = queue[k].poll().intValue();
                }
            }
        }    
        return array;
    }

计数排序：

　　前提：待排序表中的所有待排序关键字必须互不相同；

　　思想：计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c，则该记录在新的有序表中的存放位置即为c。

　　性能：空间复杂度：o(n)；时间复杂度:o(n^2)；

    public int[] countSort(int[] array){
        int[] tempArray = new int[array.length];  //引入辅助数组
        for(int i=0;i<array.length;i++){
            int count = 0;
            for(int j=0;j<array.length;j++){
                if(array[i]>array[j]){
                    count++;
                }
            }
            tempArray[count] = array[i];
        }
        return tempArray;
    }