Java中十大排序算法

左手的ㄟ右手 2024-03-31 15:34 67阅读 0赞

## 十大排序算法： ##

### 1. 冒泡排序 ###

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。

它重复的遍历过要排序的数列，一次比较相邻的两个元素，如果他们的顺序错误就把他们交换过来。

这个算法的名字由来是因为越大的元素会经由交换慢慢"浮"到最后面。

当然，大家可以按照从大到小的方式进行排列。

#### 1.1 算法步骤 ####

1.  相邻的元素两两比较，大的放右边，小的放左边
2.  第一轮比较完毕之后，最大值就已经确定，第二轮可以少循环一次，后面以此类推
3.  如果数组中有n个数据，总共我们只要执行n-1轮的代码就可以

#### 1.2 动图演示 ####

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Z6tiBhAP-1670295520933)(F:\\JavaSE最新版\\day21-API（算法，lambda，练习）\\笔记\\img\\冒泡.gif)\]

#### 1.3 代码示例 ####

public class A01_BubbleDemo {
        
        public static void main(String[] args) {
        
            /*
                冒泡排序：
                核心思想：
                1，相邻的元素两两比较，大的放右边，小的放左边。
                2，第一轮比较完毕之后，最大值就已经确定，第二轮可以少循环一次，后面以此类推。
                3，如果数组中有n个数据，总共我们只要执行n-1轮的代码就可以。
            */
     
     
            //1.定义数组
            int[] arr = {
        2, 4, 5, 3, 1};
     
            //2.利用冒泡排序将数组中的数据变成 1 2 3 4 5
     
            //外循环：表示我要执行多少轮。 如果有n个数据，那么执行n - 1 轮
            for (int i = 0; i < arr.length - 1; i++) {
        
                //内循环：每一轮中我如何比较数据并找到当前的最大值
                //-1：为了防止索引越界
                //-i：提高效率，每一轮执行的次数应该比上一轮少一次。
                for (int j = 0; j < arr.length - 1 - i; j++) {
        
                    //i 依次表示数组中的每一个索引：0 1 2 3 4
                    if(arr[j] > arr[j + 1]){
        
                        int temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
            }
     
            printArr(arr);
     
     
     
     
        }
     
        private static void printArr(int[] arr) {
        
            //3.遍历数组
            for (int i = 0; i < arr.length; i++) {
        
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    }

### 2. 选择排序 ###

#### 2.1 算法步骤 ####

1.  从0索引开始，跟后面的元素一一比较
2.  小的放前面，大的放后面
3.  第一次循环结束后，最小的数据已经确定
4.  第二次循环从1索引开始以此类推
5.  第三轮循环从2索引开始以此类推
6.  第四轮循环从3索引开始以此类推。

#### 2.2 动图演示 ####

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oL9gn73Y-1670295520942)(img\\选择排序.gif)\]

public class A02_SelectionDemo {
        
        public static void main(String[] args) {
        
     
            /*
                选择排序：
                    1，从0索引开始，跟后面的元素一一比较。
                    2，小的放前面，大的放后面。
                    3，第一次循环结束后，最小的数据已经确定。
                    4，第二次循环从1索引开始以此类推。
     
             */
     
     
            //1.定义数组
            int[] arr = {
        2, 4, 5, 3, 1};
     
     
            //2.利用选择排序让数组变成 1 2 3 4 5
           /* //第一轮：
            //从0索引开始，跟后面的元素一一比较。
            for (int i = 0 + 1; i < arr.length; i++) {
                //拿着0索引跟后面的数据进行比较
                if(arr[0] > arr[i]){
                    int temp = arr[0];
                    arr[0] = arr[i];
                    arr[i] = temp;
                }
            }*/
     
            //最终代码：
            //外循环：几轮
            //i:表示这一轮中，我拿着哪个索引上的数据跟后面的数据进行比较并交换
            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;
                    }
                }
            }
     
     
            printArr(arr);
     
     
        }
        private static void printArr(int[] arr) {
        
            //3.遍历数组
            for (int i = 0; i < arr.length; i++) {
        
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
     
    }

### 3. 插入排序 ###

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过创建有序序列和无序序列，然后再遍历无序序列得到里面每一个数字，把每一个数字插入到有序序列中正确的位置。

插入排序在插入的时候，有优化算法，在遍历有序序列找正确位置时，可以采取二分查找

#### 3.1 算法步骤 ####

将0索引的元素到N索引的元素看做是有序的，把N+1索引的元素到最后一个当成是无序的。

遍历无序的数据，将遍历到的元素插入有序序列中适当的位置，如遇到相同数据，插在后面。

N的范围：0~最大索引

#### 3.2 动图演示 ####

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KBNRE8kk-1670295520962)(img\\插入排序.gif)\]

package com.itheima.mysort;
     
     
    public class A03_InsertDemo {
        
        public static void main(String[] args) {
        
            /*
                插入排序：
                    将0索引的元素到N索引的元素看做是有序的，把N+1索引的元素到最后一个当成是无序的。
                    遍历无序的数据，将遍历到的元素插入有序序列中适当的位置，如遇到相同数据，插在后面。
                    N的范围：0~最大索引
     
            */
            int[] arr = {
        3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
     
            //1.找到无序的哪一组数组是从哪个索引开始的。  2
            int startIndex = -1;
            for (int i = 0; i < arr.length; i++) {
        
                if(arr[i] > arr[i + 1]){
        
                    startIndex = i + 1;
                    break;
                }
            }
     
            //2.遍历从startIndex开始到最后一个元素，依次得到无序的哪一组数据中的每一个元素
            for (int i = startIndex; i < arr.length; i++) {
        
                //问题：如何把遍历到的数据，插入到前面有序的这一组当中
     
                //记录当前要插入数据的索引
                int j = i;
     
                while(j > 0 && arr[j] < arr[j - 1]){
        
                    //交换位置
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                    j--;
                }
     
            }
            printArr(arr);
        }
     
        private static void printArr(int[] arr) {
        
            //3.遍历数组
            for (int i = 0; i < arr.length; i++) {
        
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
     
    }

### 4. 快速排序 ###

快速排序是由东尼·霍尔所发展的一种排序算法。

快速排序又是一种分而治之思想在排序算法上的典型应用。

快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！

它是处理大数据最快的排序算法之一了。

#### 4.1 算法步骤 ####

1.  从数列中挑出一个元素，一般都是左边第一个数字，称为 “基准数”;
2.  创建两个指针，一个从前往后走，一个从后往前走。
3.  先执行后面的指针，找出第一个比基准数小的数字
4.  再执行前面的指针，找出第一个比基准数大的数字
5.  交换两个指针指向的数字
6.  直到两个指针相遇
7.  将基准数跟指针指向位置的数字交换位置，称之为：基准数归位。
8.  第一轮结束之后，基准数左边的数字都是比基准数小的，基准数右边的数字都是比基准数大的。
9.  把基准数左边看做一个序列，把基准数右边看做一个序列，按照刚刚的规则递归排序

#### 4.2 动图演示 ####

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xBho3sbe-1670295520972)(img\\快速排序.gif)\]

package com.itheima.mysort;
    
    import java.util.Arrays;
    
    public class A05_QuickSortDemo {
        
       public static void main(String[] args) {
        
           System.out.println(Integer.MAX_VALUE);
           System.out.println(Integer.MIN_VALUE);
         /*
           快速排序：
               第一轮：以0索引的数字为基准数，确定基准数在数组中正确的位置。
               比基准数小的全部在左边，比基准数大的全部在右边。
               后面以此类推。
         */
    
           int[] arr = {
        1,1, 6, 2, 7, 9, 3, 4, 5, 1,10, 8};
    
    
           //int[] arr = new int[1000000];
    
          /* Random r = new Random();
           for (int i = 0; i < arr.length; i++) {
               arr[i] = r.nextInt();
           }*/
    
    
           long start = System.currentTimeMillis();
           quickSort(arr, 0, arr.length - 1);
           long end = System.currentTimeMillis();
    
           System.out.println(end - start);//149
    
           System.out.println(Arrays.toString(arr));
           //课堂练习：
           //我们可以利用相同的办法去测试一下，选择排序，冒泡排序以及插入排序运行的效率
           //得到一个结论：快速排序真的非常快。
    
          /* 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，从后往前开始找，找比基准数小的数字
               //int[] arr = {1, 6, 2, 7, 9, 3, 4, 5, 10, 8};
               while(true){
        
                   if(end <= start || arr[end] < baseNumber){
        
                       break;
                   }
                   end--;
               }
               System.out.println(end);
               //利用start，从前往后找，找比基准数大的数字
               while(true){
        
                   if(end <= start || arr[start] > baseNumber){
        
                       break;
                   }
                   start++;
               }
    
    
    
               //把end和start指向的元素进行交换
               int temp = arr[start];
               arr[start] = arr[end];
               arr[end] = temp;
           }
    
           //当start和end指向了同一个元素的时候，那么上面的循环就会结束
           //表示已经找到了基准数在数组中应存入的位置
           //基准数归位
           //就是拿着这个范围中的第一个数字，跟start指向的元素进行交换
           int temp = arr[i];
           arr[i] = arr[start];
           arr[start] = temp;
    
           //确定6左边的范围，重复刚刚所做的事情
           quickSort(arr,i,start - 1);
           //确定6右边的范围，重复刚刚所做的事情
           quickSort(arr,start + 1,j);
    
       }
    }