Java基础—交换排序(冒泡排序，快速排序)

1.冒泡排序

• 原理：在无序区间，通过相邻数的比较，将最大的数冒泡到无序区间的最后，持续这个过程，直到数组整体有序。

• 稳定性(稳定)
  ​ 1.一个稳定的排序可以变成不稳定的排序；
  ​ 2.一个本身就不稳定的是不可能变成稳定的；

• 空间复杂度：O(1)

• 时间复杂度：最好情况O(n)；最坏情况O(n^2)

//冒泡排序
    public static void bubbleSort(int[] arr){
        for (int i = 0;i < arr.length-1;i++){//控制冒泡次数
            for(int j = 0;j < arr.length-1-i;j++){
                if (arr[j] > arr[j+1]){
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }
    }

2.快速排序

• 原理：
  1.从待排序区间选择一个数，作为基准值(pivot)；
  2. Partition: 遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的（可以包含相等的）放到基准值的右边；
  3. 采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间的长度 == 1，代表已经有序，或者小区间的长度 == 0，代表没有数据。
• 稳定性(不稳定)

​ 1.一个稳定的排序可以变成不稳定的排序；

​ 2.一个本身就不稳定的是不可能变成稳定的；

• 空间复杂度：O(log2n)
• 时间复杂度：度：O(n*logn)

//快速排序
public static void quicksort(int[] arr){
        quick(arr,0,arr.length-1);

    }
    //排序
    public static void quick(int[] arr,int low,int high){
        if(low > high){
            return;
        }
        //par是基准
        int par = parttion(arr,low,high);
        quick(arr,low,par-1);
        quick(arr,par+1,high);
    }
    //划分函数
    public static int parttion(int[] arr,int start,int end){
        //申请一个tmp空间用来放基准的值(基准一般选择的是边上的值)
        int tmp = arr[start];//这里取的是最左边的值，那么一会就先从最右边开始找[end]位置
        while(start < end){
            while(start < end && arr[end] >= tmp){
                end--;
            }
            //到了这里，从while出来有俩种情况，不满足start < end或者不满足arr[end] >= tmp
            if (start >= end){
                //arr[start] = tmp;
                break;//直接退出，因为已经遍历完毕
            }else{//else就是arr[end] < tmp
                arr[start] = arr[end];
            }
            while(start < end && arr[start] <= tmp){
                start++;
            }
            //到了这里，同样从while出来有俩种情况，不满足start < end或者不满足arr[start] <= tmp
            if (start > end){
                //arr[end] = tmp;
                break;
            }else{
                arr[end] = arr[start];
            }
        }
        arr[start] = tmp;
        return start;//返回基准移动到位置，这样基准的左边全小于它，右边全都大于它

3.结果测试

public class TestSort {
//冒泡排序
    public static void bubbleSort(int[] arr){
        for (int i = 0;i < arr.length-1;i++){//控制冒泡次数
            for(int j = 0;j < arr.length-1-i;j++){
                if (arr[j] > arr[j+1]){
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }
    }
//快速排序
public static void quicksort(int[] arr){
        quick(arr,0,arr.length-1);

    }
    //排序
    public static void quick(int[] arr,int low,int high){
        if(low > high){
            return;
        }
        //par是基准
        int par = parttion(arr,low,high);
        quick(arr,low,par-1);
        quick(arr,par+1,high);
    }
    //划分函数
    public static int parttion(int[] arr,int start,int end){
        //申请一个tmp空间用来放基准的值(基准一般选择的是边上的值)
        int tmp = arr[start];//这里取的是最左边的值，那么一会就先从最右边开始找[end]位置
        while(start < end){
            while(start < end && arr[end] >= tmp){
                end--;
            }
            //到了这里，从while出来有俩种情况，不满足start < end或者不满足arr[end] >= tmp
            if (start >= end){
                //arr[start] = tmp;
                break;//直接退出，因为已经遍历完毕
            }else{//else就是arr[end] < tmp
                arr[start] = arr[end];
            }
            while(start < end && arr[start] <= tmp){
                start++;
            }
            //到了这里，同样从while出来有俩种情况，不满足start < end或者不满足arr[start] <= tmp
            if (start > end){
                //arr[end] = tmp;
                break;
            }else{
                arr[end] = arr[start];
            }
        }
        arr[start] = tmp;
        return start;//返回基准移动到位置，这样基准的左边全小于它，右边全都大于它
}


//测试main方法
public static void main(String[] args) {
//冒泡排序
        int[] arr3 = {7,4,9,34,0,8,5,22,55,6,12,33,56,89,77};
        bubbleSort(arr3);
        System.out.print("冒泡排序结果: ");
        for (int i = 0;i < arr3.length;i++){
            System.out.print(arr3[i]+" ");
        }
        //快速排序
        int[] arr5 = {7,4,9,34,0,8,5,22,55,6,12,33,56,89,77};
        quicksort(arr5);
        System.out.print("快速排序结果: ");
        for (int i = 0;i < arr5.length;i++){
            System.out.print(arr5[i]+" ");
        }
}

本文地址：https://blog.csdn.net/qq_45665172/article/details/109648630