排序算法Java

冷不防 2022-05-25 05:58 140阅读 0赞

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

![这里写图片描述][70]  
当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。

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

## 1.冒泡排序 ##

![这里写图片描述][70 1]  
关键代码：  
import java.util.Arrays;

/*冒泡排序： 每趟结果将最大的数选择出来，放在数组的最后*/
    public class BubbleSort {
    
        public static void main(String[] args) {
            int[] test = {
       1,2,4,5,6,2,3};
            int[] sort = sort(test);
            System.out.println(Arrays.toString(sort));
        }
    
        public static int[] sort(int[] A){
            for(int i = 0; i<A.length; i++){
                for(int j= i+1; j<A.length; j++){
                    if(A[i] > A[j]){
                        int tmp = A[i];
                        A[i] = A[j];
                        A[j] = tmp; 
                    }
                }
            }
            return A;
        }
    }

分析：  
冒泡排序是一种稳定的排序方法。

•若文件初状为正序，则一趟起泡就可完成排序，排序码的比较次数为n-1，且没有记录移动，时间复杂度是O(n)  
•若文件初态为逆序，则需要n-1趟起泡，每趟进行n-i次排序码的比较，且每次比较都移动三次，比较和移动次数均达到最大值∶O(n2)  
•起泡排序平均时间复杂度为O(n2)

## 2.快速排序 ##

选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。

/*快速排序： 选择一个基准，将数组分成两部分；比基准大的一部分，比基准小的一部分； 然后重复此过程*/
    public class QuickSort {
    
        public static void main(String[] args) {
            int[] a = {
       2,8,4,5,3,5,4,8,14,54,23};
            sort(a,0,a.length-1);
            System.out.println(Arrays.toString(a));
        }
        //做递归
        public static void sort(int[] a, int left, int right){
            if(left < right){
       //如果不加这个判断递归会无法退出导致堆栈溢出异常 
                int mid = partion(a, left, right);
                sort(a, left, mid - 1);//递归对低子表递归排序
                sort(a, mid + 1, right); //递归对高子表递归排序
            }
        }
        private static int partion(int[] a, int low, int high) {
            int key = a[low];//基准元素，排序中会空出来一个位置 
            while(low<high){  
                while(low<high && a[high]>=key){
       //从high开始找比基准小的，与low换位置 
                    high--;  
                }  
                a[low]=a[high];  
                while(low<high && a[low]<=key){
       //从low开始找比基准大,放到之前high空出来的位置上 
                    low++;  
                }  
                a[high]=a[low];  
            }  
            a[low]=key;//此时low=high 是基准元素的位置，也是空出来的那个位置 
            return low; 
        }
    }

## 3、折半插入排序（二分法插入排序） ##

折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。

private static void binaryInsertSort(int[] array) {  
        for(int i=1;i<array.length;i++){  
         int tempData=array[i];  
         int low=0;  
         int high=i-1;  
         while(low<=high){  
             int middle=(low+high)/2;  
             if(array[middle]<tempData)  
                 low=middle+1;  
             else  
                 high=middle-1;  
         }  
         System.arraycopy(array,low,array,low+1,i-low);  
         array[low]=tempData;  
        }  
    }

[70]: /images/20220525/661d4071a5b44ac19cf5ccd6926c4fec.png
[70 1]: /images/20220525/acf7cabea64742a48ebbe86356be64bb.png