java 常用算法--复习笔记--基本排序算法

待我称王封你为后i 2022-06-02 23:35 211阅读 0赞

–本文参考书目《java常用算法手册》赵志云，衡友跃，中国铁道出版社。

![算法分类][SouthEast]

1、冒泡排序算法   
冒泡排序思路就是交换排序，通过相邻数据的交换来达到排序的目的。对N个数据排序时，无论原数据有无数据，都需要进行N-1步的中间排序。   
缺点：执行效率不是很高。   
改进：在每次中间排序之后，比较一下数据是否已经按照顺序排列完成。若排列完成则退出排序过程，否则继续进行冒泡排序，这样对于数据比较有规则的，可以加速算法的执行过程。

void bubbleSort(int[] a){ 
            int temp; 
            for(int i=1; i<a.length; i++){ 
                for(int j=0; j<a.length-i; j++){ 
                    if(a[j]>a[j+1]){ 
                        temp = a[j]; 
                        a[j] = a[j+1];
                        a[j+1]=temp; 
                    }
                }
                System.out.print("第"+i+"步排序结果："); 
                for(int k=0; k<a.length; k++){    
                    System.out.print(" "+a[k]); 
                }
                System.out.println(); 
                }
         }

2、选择排序算法   
在每一步中选取最小值来重新排列，来达到排序目的。   
流程：（1）首先从原始数组中选择最小的1个数据，将其和位于第一个位置的数据交换； （2）接着从剩下的n-1个数据中选择次小的1个元素，将其和第二个位置的数据交换； （3）然后，不断重复，直到最后两个数交换完成。至此，完成对原始数据从小到大的排序。   
N个数据需要N-1步的中间排序。

void insertSort(int[] a){ 
            int N = a.length;
            for(int i=0; i<N; i++){
                int minNumIndx = i;
                //循环从后边找最小元素下标，减少交换次数
                for(int j=i+1; j<N; j++){
                    if(a[j] < a[minNumIndx])
                        minNumIndx = j;
                }
                swap(a, i, minNumIndx);
            }
             /* 另一个版本 
             int j,t,h; 
             for(int i=1; i<a.length; i++){ 
                 t = a[i]; 
                 j = i-1; 
                 while(j>=0&&t<a[j]){ 
                     a[j+1] = a[j]; 
                     j--; 
                } 
                a[j+1]=t;
            } */
        }
        void swap(int[] a, int i, int j){
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }

4、Shell排序法（希尔排序/缩小增量排序）

void shellSort(int[] a){ 
             int j,i,h; 
             int r,temp; 
             int x=0; 
             for(r = a.length/2; r>=1; r/=2){ 
                 for(i=r; i<a.length; i++){ 
                     temp = a[i]; 
                     j=i-r; 
                     while(j>=0&&temp<a[j]){ 
                         a[j+r] = a[j]; 
                         j-=r; 
                    } 
                    a[j+r] = temp; 
                } 
                x++; 
                //输出每步排序结果 
                System.out.print("第"+x+"步排序结果："); 
                for(int k=0; k<a.length; k++){ 
                    System.out.print(" "+a[k]); 
                } 
                System.out.println(); 
            } 
        }

5、快速排序法   
与冒泡排序类似，都是基于交换排序思想。对冒泡排序的改进，有更高的执行效率。   
（1）首先选取一个分界值，将数组分成左右两部分；   
（2）将大于等于分界值的数据集中到数组右边，小于的集中到数组左边。此时，左边的各元素都小于分界值，右边的各元素都大于等于分界值。   
（3）然后左边和右边的数据可以独立排序。对于左侧的数据又可以取分界值分为左右两部分，左边放置较小值，右边放置较大值。右侧数组数据类似处理。   
（4）重复上述过程，通过递归，将左右两侧数据排好序后，整个数组的排序就完成了。

public void sort(int[] a, int lo, int hi){
        if(lo >= hi) return;
        int j = partition(a, lo, hi);
        sort(a, lo, j-1);
        sort(a, j+1, hi);
    }
    
    public int partition(int[] a, int lo, int hi){
        int i = lo, j = hi+1;
        int v= a[lo]; //一般以第一个元素为支点
        while(true){
            while(a[++i] < v) if(i == hi) break;
            while(v < a[--j]) if(j == lo) break;
            if(i>=j) break;
            swap(a, i, j);
        }
        swap(a, lo, j);
        return j;
    }

6、堆排序法   
堆排序法是基于选择排序思想的，利用堆结构和二叉树的一些性质来完成数据排序。   
A 什么是堆结构？   
堆结构是一种树结构，准确的说是一个完全二叉树。   
树中每个结点对应原始数据的一个记录，每个结点满足如下条件：   
\*若按照从小到大顺序排序，要求非叶结点数据>=其左右子结点的数据；   
\*若按照从大到小顺序排序，要求非叶结点数据<=其左右子结点的数据；   
(对结点的左子结点和右子结点大小无要求。)   
B 堆排序过程   
反复两个步骤：构造堆结构和堆排序输出。

//1.将无序数组构建为最大堆（最大堆调整后数组是升序排序）时间复杂度为O(N)
    //2.每次将堆顶元素和“最后一个”元素交换(最后一个元素指不断调整后次大元素)后，调整堆 ，时间复杂度是O(NLogN)
    
    public void heapSort(int[] a){
        if(a == null || a.length == 0) return;
        buildHeap(a);
        int n = a.length-1;
        for(int i=0; i<n; i++){
            swap(a, i, n--); 
            sink(a, i, n);
        }
    }
    
    public void buildHeap(int[] a){
        int N = a.length;
        for(int i=N/2-1; i>=0; i--)
            sink(a, i, N-1);
    }
    public void sink(int[] a, int k, int N){
        //int tmp = a[k];
        while(2*k <= N){
            int j = 2*k;
            if(j<N && a[j] < a[j+1])
                j++; //右孩子比左孩子要大，j为右孩子结点。因为构建的最大堆，所以堆顶要大于两个孩子结点，当然要大于两个孩子中的最大的那个。
            if(a[k] >= a[j]) break;
            swap(a, k , j);
            k = j; //因为调整了堆顶结点，因此下边的结点受影响也要调整
        }
    }
    
    public void swap(int[] a, int i, int j){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

参考：[https://blog.csdn.net/jianyuerensheng/article/details/51263453][https_blog.csdn.net_jianyuerensheng_article_details_51263453]

7、归并排序

先递归分成两个子数组，再合并为一个数组。

public void sort(int[] a, int lo, int hi){
        if(lo >= hi) return;
        int mid = lo + (hi-lo)/2;
        sort(a, lo, mid);
        sort(a, mid+1, hi);
        merge(a, lo, mid+1, hi);
    }
    
    public void merge(int[] a, int lo, int mid, int hi){
        if(lo >= hi) return;
        int[] copy = new int[a.length];
        //辅助数组
        for(int i=lo; i<=hi; i++)
            copy[i] = a[i];
        //合并
        int i=lo, j=mid, indx = 0;
        while(i<mid && j<=hi){
            if(a[i] < a[j])
                copy[indx++] = a[i++];
            else
                copy[indx++] = a[j++];
        }
        while(i<mid){
            copy[indx++] = a[i++];
        }
        while(j<=hi){
            copy[indx++] = a[j++];
        }
        //复制回原数组
        for(int k = lo; k<=hi; k++)
            a[k] = copy[k];
    }

排序算法的效率：

![SouthEast 1][]

[SouthEast]: /images/20220603/426f59a473694a8e9768a97692c5e2c3.png
[https_blog.csdn.net_jianyuerensheng_article_details_51263453]: https://blog.csdn.net/jianyuerensheng/article/details/51263453
[SouthEast 1]: /images/20220603/819897ee80f241508601e6edb00f956d.png