两种排序算法

分手后的思念是犯贱 2024-03-16 20:02 50阅读 0赞

## **1、冒泡排序** ##

**基本思想：**现在有一个数组arr= \{12,35,99,18,76\}，需要将其从小到大排序

1.  **第一次冒泡：**首先我们将数组第一个数（arr\[0\]）和第二个数（arr\[1\]）进行比较，如果第二个数比第一个数大，那么将两个数字进行交换，交换完成的数组是arr=\{35,12,99,18,76\}，这时候前两个数已经是满足最小的数在后面；第二步，比较第二数（arr\[1\]）和第三个数（arr\[2\]），发现99比12大，则进行交换，第二步完成的数组是arr=\{35,99,12,18,76\}，以此类推，接着比较剩下来的数，最后最小的数12将来到数组的最后一位，第一次冒泡排序完的数组是arr=\{35,99,18,76,12\}
2.  **第二次冒泡：**首先还是比较第一个数和第二个数，99比35大，则进行交换，交换后数组是arr=\{99,35,18,76,12\}；第二步比较第二个数和第三个数，35比18大，则不需要进行交换，第二步后结果是arr=\{99,35,18,76,12\}；第三步比较第三个数和第四个数，18比76小，则进行交换，交换后数组是arr=\{99,35,76,18,12\}；第一次冒泡后最小的数12已经在数组的最后一位了，那么第二次冒泡则不需要比较数组最后一位数，第二次冒泡完成
3.  **第三次冒泡：**排序后结果：arr=\{99,76,35,18,12\}
4.  **第四次冒泡：**排序后结果：arr=\{99,76,35,18,12\}，至此冒泡排序结束

**代码：**

1 public static void BubbleSort(int[] arr) {
     2         //外层循环控制冒泡次数
     3         for(int i=0;i<arr.length;i++) {
     4             //内层循环进行比较
     5             for(int j=0;j<arr.length-i-1;j++) {
     6                 int temp=0;
     7                 //如果前一个比后一个数小,则进行交换,这里借用临时变量temp进行交换
     8                 if(arr[j]<arr[j+1]) {
     9                     temp=arr[j];
    10                     arr[j]=arr[j+1];
    11                     arr[j+1]=temp;
    12                 }
    13             }
    14         }
    15 }

复制

## 2、选择排序： ##

**原理**：每一次循环从未排序的数中找出最小的数，然后与已经排好序的数的下一个数进行交换，直到全部记录排序完毕

**基本思想：**给定数组：int\[\] arr=\{里面n个数据\}，第一次排序从arr\[0\]~arr\[n-1\]中找出最小的数据，然后将这个最小的数与arr\[0\]交换；第二次排序从arr\[1\]~arr\[n-1\]找出最小的数，然后将这个最小的数与arr\[1\]交换，以此类推，第i次排序在arr\[i-1\]~arr\[n-1\]中找出最小的数与arr\[i-1\]交换，直到全部排序完毕。

**例子：**

数组 int\[\] arr=\{2,8,3,7,5,6\};

\-------------------------------------------------------

第一趟排序： 原始数据：2 8 3 7 5 6

最小数据2，把2放在首位，2原来就在首位，不需要交换

排序结果：2 8 3 7 5 6

\-------------------------------------------------------

第二趟排序： 原始数据：8 3 7 5 6(2已经排好序了，不需要再排序了)

最小数据3，8和3交换

排序结果：2 3 8 7 5 6

\-------------------------------------------------------

第三趟排序： 原始数据：8 7 5 6(2、3已经排好序了，不需要再排序了)

最小数据5，5和8交换

排序结果：2 3 5 7 8 6

\-------------------------------------------------------

第四趟排序： 原始数据：7 8 6(2、3、5已经排好序了，不需要再排序了)

最小数据6，6和7交换

排序结果：2 3 5 6 8 7

\-------------------------------------------------------

第五趟排序： 原始数据：8 7(2、3、5、6已经排好序了，不需要再排序了)

最小数据7，7和8交换

排序结果：2 3 5 6 7 8

排序完成

**代码示例：**

1 package com.alibaba;
     2 
     3 import org.junit.jupiter.api.Test;
     4 
     5 /**
     6  * 选择排序
     7  * @author wydream
     8  *
     9  */
    10 
    11 public class SelectSort {
    12     
    13     public void sort(int[] arr) {
    14         if(arr==null||arr.length==0) {
    15             return;
    16         }
    17         
    18         for(int i=0;i<arr.length;i++) {
    19             int temp=arr[i];//记录最小的数
    20             int flag=i;//记录最小数的下标
    21             for(int j=i;j<arr.length;j++) {
    22                 if(arr[j]<arr[flag]) {
    23                     temp=arr[j];//和最小数交换位置
    24                     flag=j;//最小数下标变化
    25                 }
    26             }
    27             if(flag!=i) {//如果最小数不是arr[i] 则交换数据
    28                 arr[flag]=arr[i];
    29                 arr[i]=temp;
    30             }
    31         }
    32     }
    33     
    34     @Test
    35     public void test() {
    36         int[] arr= {2,8,3,7,5,6};
    37         sort(arr);
    38         for (int i : arr) {
    39             System.out.println(i);
    40         }
    41     }
    42 
    43 }