JAVA算法—排序

目录

*冒泡排序：

*选择排序：

插入排序：

快速排序：

总结：

---

以下全部以升序为例

---

*冒泡排序：

引用：

在完成升序排序时，最大的元素会经过一轮轮的遍历逐渐被交换到数列的末尾，就像气泡从水底慢慢升到水面的过程。这个过程会重复进行，直到整个序列有序，即没有更多的“气泡”需要“上浮”。

步骤（针对于升序）：

1. 从 0 索引开始向后，相邻元素两两相比（索引 0 和 1、 1 和 2 ），小的放在左，大的放在右。

如上面动图，在最大的数放置在最右边后，这样就完成了第一轮排序，这一轮中确定了最大值

1. 在第二轮中仍然从 0 索引开始，在剩余元素中两两比较。每一轮都可以确定一个组内最大值
2. 如果数组中有n个数据，总共我们只要执行n-1轮就可以，如针对数组{6，9，3，1}

第一轮流程：

6-9 9-3 3-1 确定了索引 3 位置上的最大值

第二轮流程：

6-9 9-3 确定了索引 2 位置上的次大值

第三轮流程：

6-9 确定了索引 1 位置上的次次大值

索引 0 显然不用再去比较，因为已经有三个数字大小关系已被确认，索引 0 就可以被默认确认。

代码演示

//1.定义数组---要求从小到大排序
int[] arr = {5, 9, 7, 3, 4};

//外循环：表示我要执行多少轮。 如果有n个数据，那么执行n - 1 轮
for (int i = 0; i < arr.length-1; i++) {
//内循环表示我们在每一轮内要做什么：从 0 索引开始向后，两两比较
//-1：为了防止arr[j + 1]索引越界
//-i：提高效率，每一轮执行的次数应该比上一轮少一次。0、1、2、3
    for (int j = 0; j < arr.length - 1-i; j++) {
        if (arr[j] > arr[j + 1]) {
            //定义临时变量交换数据
            int num = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = num;
        }
    }
}

//遍历检验
for (int i1 = 0; i1 < arr.length; i1++) {
    System.out.print(arr[i1] + " ");
}
}

控制台：

3 4 5 7 9

---

*选择排序：

引用：

步骤（针对于升序）：

1. 从0索引开始，将 0 索引跟后面的元素一 一比较

小的放左，大的放右

第一轮结束后，最小的数据已经确定，在最左侧。

1. 所以第二轮直接从1索引开始跟后面的元素一 一比较

以此类推....

1. 如果数组中有n个数据，总共我们只要执行n-1轮就可以如数组{2，7，5，4}

第一轮：

2-7 2-5 2-4

第二轮：

7-5 7-4

第三轮：

5 - 4

第四轮没必要走了，4 不可能和自己比较

int[] arr = {6, 4, 8, 9, 5};

//外循环表示要走的轮数，
/*第一轮：6和其余四个比较  第二轮：4和其余三个比较....
......第四轮：9和5比较*/
for (int i = 0; i < arr.length - 1; i++) {
//内循环：每一轮我要干什么事情：拿着i跟i后面的数据进行比较交换
    for (int j = i + 1; j < arr.length; j++) {
        if (arr[i] > arr[j]) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
}
//遍历检验
for (int i1 = 0; i1 < arr.length; i1++) {
    System.out.println(arr[i1]);
}

控制台：

4 5 6 8 9

---

插入排序：

和打扑克牌一样，

步骤（针对升序数组）：

1. 将 0 索引的元素到 N 索引的元素看做是有序的，其后元素则看作是无序的。

1. 遍历后面那些无序的元素，将遍历到的元素插入有序序列中适当的位置，如遇到相同数据，插在后面。
2. 每遍历并排序完一个无序元素后，有序序列就会多一个元素，无序序列就会少一个元素。
3. 如下引用动图：

代码实现：

int[] arr = {3, 44,
             38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
//显然看得出3，44有序


//先找到无序序列的开始索引
int startInsert=-1;
for (int i = 0; i < arr.length; i++) {
    //注意这里针对的是升序
    if (arr[i]>arr[i+1]){
        startInsert=i+1;//2
        break;
    }
}

//所以说无序的开始索引是2（38）
//现在遍历无序序列
for (int i =startInsert ; i <arr.length ; i++) {
    int j=i;//第一次为2，每轮结束后都会向后移一个
    
    //这里判断条件顺序不能变
    while(j>0&&arr[j]<arr[j-1]){
        int temp=arr[j];
        arr[j]=arr[j-1];
        arr[j-1]=temp;
        j--;
    }
}

for (int i = 0; i < arr.length; i++) {
    System.out.print(arr[i]+" ");
}

控制台

2 3 4 5 15 19 26 27 36 38 44 46 47 48 50

针对这段代码，解释下逻辑：

startInsert 已经知道是无序索引 2 了

i=2 进去，赋值给 j =2 ，j 用于与有序序列比较，while 括号内逻辑：若 j>0 并且，索引 2 的值小于和索引 1 的值，那么它们就交换位置， 然后 j--，索引 1 和索引 0 的值比较

之后 j 无发再--，此时有序序列为 2、 38、 44

跳出 while，i++,为 3，...以此类推

---

快速排序：

引用：

1. 从数列中挑出一个元素，一般都是左边第一个数字，称为 "基准数";

2. 创建两个指针，一个从前往后走，一个从后往前走。

3. 先执行后面的指针，找出第一个比基准数小的数字

4. 再执行前面的指针，找出第一个比基准数大的数字

5. 交换两个指针指向的数字

之后不断找，不断交换

6. 直到两个指针相遇

7. 将基准数跟指针指向位置的数字交换位置，称之为：基准数归位。

8. 第一轮结束之后，基准数左边的数字都是比基准数小的，基准数右边的数字都是比基准数大的。

9. 把基准数左边看做一个序列，把基准数右边看做一个序列，按照刚刚的规则递归排序

int[] arr = {6,1,2,7,9, 3, 4, 5,10, 8};

quickSort(arr,0,arr.length-1);//参数：数组、排序数组开始、结束索引

//遍历检验
for (int i = 0; i < arr.length; i++) {
    System.out.print    (arr[i]+" ");
}

----------------------------------------------------
public static void quickSort(int [] arr,int i,int j){
    //定义两个变量记录要查找的范围
    int start=i;
    int end=j;

    //递归出口
    if (start>end){
        return;
    }


    //记录基准数--每轮结束后都会向后移一个
    int baseNumber=arr[i];
    //利用循环找到要交换的数字
    while(start!=end){
        //利用end，从后往前开始找，找比基准数小的数字
        while(true){
            if (end<=start||arr[end]<baseNumber){
                break;//end和start重合 或 找到了 就跳出循环
            }
            //否则继续向前找
            end--;
        }
        //利用start，从前往后找，找比基准数大的数字
        while(true){
            if (end<=start||arr[start]>baseNumber){
                break;//end和start重合或 找到了 就跳出循环
            }
            //否则继续向后找
            start++;
        }
        //把end和start指向的元素进行交换
        int temp=arr[start];
        arr[start]=arr[end];
        arr[end]=temp;
        //交换完继续循环，找下一对可交换的数，直到start=end时停止
    }
    //当start和end指向了同一个元素的时候，那么上面的循环就会结束
    //*start和end指向同一个元素的位置就是基准数应存入的位置*

//现在就该基准数归位了
//就是拿着这个范围中的第一个数字arr[i]，跟start或end指向的元素进行交换
    int temp=arr[i];
    arr[i]=arr[start];
    arr[start]=temp;
    //确定刚刚归位数左边的范围，重复刚刚所做的事情
    quickSort(arr,i,start-1);
    //确定刚刚归位数右边的范围，重复刚刚所做的事情
    quickSort(arr,start+1,j);
}

• 最后是使用了递归算法
• 最后的 基准数归位和递归算法中的 start 换成 end 也行，因为它们最后都指向了同一个位置
• 读代码要有耐心

---

总结：