package com.Sorting.bubblesort;

/**
 * @author wang
 * @packageName com.Sorting.bubblesort
 * @className Bubble
 * @date 2021/11/11 23:24
 */
public class Bubble {
    //冒泡排序，升序
    public static void bubbleSort(int[] arr) {
        //定义一个变量，判断是否有交换
        boolean exchange = true;

        //双层for循环，外层循环控制是否进行下一次冒泡
        for(int i = 1;i<arr.length && exchange;i++) {
            //入果下层循环没有进入if语句，说明没有交换存在，外层循环结束
            exchange = false;
            for(int j = 0;j<arr.length-i;j++) {
                //内层循环比较相邻两个元素大小，如果前一个元素大于后一个元素，则调用swap方法两数交换
                if(arr[j]>arr[j+1]) {
                    swap(arr,j,j+1);
                    //发生交换
                    exchange = true;
                }
            }
        }
    }
    public static void swap(int[] arr,int i,int j) {
        //交换两个数据
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
}

测试类：?

package com.Sorting.bubblesort;

import java.util.Arrays;

/**
 * @author wang
 * @packageName com.Sorting.bubblesort
 * @className BubbleTest
 * @date 2021/11/11 23:39
 */
public class BubbleTest {
    public static void main(String[] args) {
        int [] arr = {6,2,4,3,5,1};
        Bubble.bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
/*
输出结果
[1, 2, 3, 4, 5, 6]
 */

????????2.3冒泡排序算法分析

GIF小表情包 [为小表情控收集的可爱迷你动态表情包]

? GIF小表情包 [为小表情控收集的可爱迷你动态表情包]

? ? ? ? 冒泡排序我们分析他的两种情况：

1.最好情况：数据序列排序，那么只进行一次冒泡，比较n此，时间复杂度为O(n).

2.最坏情况：数据反序排列或者随机排列，那么数据就会进行n-1此冒泡，因为我们最后一趟冒泡n已经排好，所以我们要进行n-1此冒泡，大家可以自行画图理解。比较次数和移动次数都是（n-1）+(n-2) +.....+2+1；最后可以得到其时间复杂度为O(n2)。那么我们的冒泡排序即在越接近有序的情况下，他的算法的时间效率就越高，反之，如果我的数据有成千上万个，且刚好反序，那么我的效率就十分的低了。因此，冒泡排序虽然稳定，但是也难免会造成效率低下。那么接下来我们就可以学习另一种高级一点的排序方式，快速排序。

三、快速排序

? ? ? ? 3.1快速排序算法描述

? ? ? ? 在数据序列中选择一个元素作为基准值，每趟从数据序列的两端开始交替进行，将小于基准值的元素交换到序列前端，将大于基准值的元素交换到序列后端，介于两者之间的位置则成为基准位置的最终位置，同时，序列将会被划分成为两个子序列，分别对两个子序列进行快速排序，直到子序列长度为1，则完成排序。

????????那么我们通过图来理解

首先我们有一组数组int[] arr = {6,1,2,3,8,9,4,5,7};

?????????目前数组这样排序，我们可以给定一个low指针，来指向数组中第一个元素，high指针来指向最后一个元素，首先我们先比较high的值7与基准元素的值6，发现7大于6，就将high的位置向左移动，直到high的值小于或等于基准元素的值，比如5时，我们交换5与6，使得high位置的值为6，low位置的值为5；接下来从low位置向右开始找，找到元素比基准元素值小，例如5,1,2,3,均比基准元素6小，那么我们就将low的值移动到直到8，这时，8>6,那么应该将8与6的位置交换，因为，大的元素始终在右边，小的元素始终在右边（升序排序），接下来我们就会得到这样一个结果

?????????这时我们的low与high还是不相等，说明排序还没有完成，继续将high的值与左边的值相比较，一样的道理，high值与基准元素比较，如果大于6，high的值向左进，low的值与其比较，如果小于，则向右进，排序完结果如下，

?????????????????当我们在继续进行下一次排序循环时，结果如下：

????????这时我们的 low值与high值已经相等，我们就退出循环，这时第一趟排序就已经完成，我们发现其实此时的数组并未按照升序进行排序，此时就需要调用递归对基准元素左边数组，右边数组分别进行以上排序，递归进行排序就可以了。那么java版代码实现如下

????????3.2快速排序代码实现

package com.Sorting.quickSort;



/**
 * @author wang
 * @packageName com.Sorting.quickSort
 * @className QSort
 * @date 2021/11/16 22:57
 */
public class QSort {
    public static void main(String[] args) {
        int[] arr = {6,1,2,3,8,9,4,5,7};
        QuickSort(arr,0,arr.length-1);
        for(int i : arr) {
            System.out.print(i + " ");
        }
        
        //输出结果：1 2 3 4 5 6 7 8 9 

    }

    public static void QuickSort(int[] arr,int low,int high) {
        int pivot;
        if(low<high) {
            pivot = partition(arr,low,high);

            //对基准值左边数组进行排序，基准值减一即从索引0处的值到基准值前一个元素参与下一次排序
            QuickSort(arr,low,pivot-1);
            //同理，对基准值右边数组进行递归排序，从基准值后一个元素到最后一个元素的值进行排序
            QuickSort(arr,pivot+1,high);
        }
    }

    public static int partition(int[] arr,int low,int high) {

        //记录一个关键值，例如数组中第一个元素
        int pivotKey = arr[low];

        //当low的位置小于high的位置时，循环结束
        while(low<high) {
            //当high处的值大于基准位置的值时，进入循环，当其值小于基准值时，退出循环
            while(low<high && arr[high] >= pivotKey) {
                high--;
            }
            //退出循环后，应该将此时的high的值和low处的值交换，也就是将high处的值与基准值进行交换
            swap(arr,low,high);

            //与上面同理
            while(low<high && arr[low] <= pivotKey) {
                low++;
            }
            swap(arr,low,high);
        }
        //返回关键字所在位置，这里返回low，high皆可，因为当low==high循环结束
        return low;
    }

    public static void swap(int[] arr,int i,int j) {
        //交换两个数据
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
}