自学内容网 自学内容网

排序算法。

***冒泡排序:

基本:

 private static void sort(int[] a){
        for (int i = 0; i < a.length-1; i++) {
            for (int j = 0; j < a.length-i-1; j++) {
                if (a[j]>a[j+1]){
                    swap(a,j,j+1);
                }
            }
        }
    }
private static void swap(int[] a,int i,int j){
        int temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }

优化一:
 

private static void sort2(int[] a){
        for (int i = 0; i < a.length-1; i++) {
            boolean swapped=false;
            for (int j = 0; j < a.length-i-1; j++) {
                if (a[j]>a[j+1]){
                    swap(a,j,j+1);
                    swapped=true;
                }
            }
            if (!swapped){
                break;
            }
        }
    }
private static void swap(int[] a,int i,int j){
        int temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }

优化二:
 

private static void sort1(int[] a){
        int n=a.length-1;
        while (true){
            int last=0;
            for (int j = 0; j <n; j++) {
                if (a[j]>a[j+1]){
                    swap(a,j,j+1);
                    last=j;
                }
            }
            n=last;
            if (n==0){
                break;
            }
        }
    }
    private static void swap(int[] a,int i,int j){
        int temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }
*****选择排序:

将数组划分为有序和无序,每一轮都选择一个最小的值加入到已排序部分。

private static void sort1(int[] a){
        for (int i = 0; i < a.length; i++) {
            int minIndex=i;
            for (int j = i+1; j <a.length; j++) {
                if (a[minIndex]>a[j]){
                    minIndex=j;
                }
            }
            if (minIndex!=i){
                swap(a,minIndex,i);
            }
           
        }
    }
    private static void swap(int[] a,int i,int j){
        int temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }

插入排序:
 
//插入排序
    private static void sort(int[] a){
        //i为待插入元素
        for (int i = 1; i < a.length; i++) {
            int t=a[i];
            for (int j = i-1; j>=0; j--) {
                if (a[j] > t) {
                    a[j + 1] = a[j];
                } else {
                    a[j + 1] = t;
                    break;
                }
            }
        }
    }
希尔排序:插入排序的优化版本

希尔排序是一种基于插入排序的排序算法,也称为缩小增量排序。它通过将待排序的数组分割成若干个子序列,分别对每个子序列进行插入排序,最后再对整个数组进行一次插入排序。

具体步骤如下:
1. 选择一个增量序列,通常为n/2、n/4、n/8等,依次对数组进行分组。
2. 对每个分组进行插入排序。
3. 逐渐减小增量,重复步骤2,直到增量为1。
4. 最后对整个数组进行一次插入排序。

希尔排序的时间复杂度取决于增量序列的选择,通常情况下为O(n log n)。相比于插入排序,希尔排序在大规模数据的排序中效率更高。
 

9,23,19,18,23,15->9,15, 19,18,23,23->9,15,18,19,23,23

****快速排序:

单边快排:选择最右侧元素为基准点元素,从左向右找一个比基准点元素大的元素,交换,然后从右向左找一个比基准点小的元素。

 


原文地址:https://blog.csdn.net/m0_71894372/article/details/137809695

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!