各种排序算法-Java-冒泡、选择、插入、快速、归并排序

我会带着你远行 2022-06-13 07:11 218阅读 0赞

> 文末有各排序算法的比较

## 冒泡排序： ##

> 1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。  
> 2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。  
> 3、针对所有的元素重复以上的步骤，除了最后一个。  
> 4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

原始数组 | 6 | 2 | 4 | 1 | 5 | 9 |

> 第一趟排序(外循环)  
> ①两两比较6 > 2交换(内循环)  
> 交换前状态| 6 | 2 | 4 | 1 | 5 | 9 |  
> 交换后状态| 2 | 6 | 4 | 1 | 5 | 9 |  
> ②两两比较,6 > 4交换  
> 交换前状态| 2 | 6 | 4 | 1 | 5 | 9 |  
> 交换后状态| 2 | 4 | 6 | 1 | 5 | 9 |  
> ③两两比较,6 > 1交换  
> 交换前状态| 2 | 4 | 6 | 1 | 5 | 9 |  
> 交换后状态| 2 | 4 | 1 | 6 | 5 | 9 |  
> ④两两比较,6 > 5交换  
> 交换前状态| 2 | 4 | 1 | 6 | 5 | 9 |  
> 交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |  
> ⑤两两比较,6 < 9不交换  
> 交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |  
> 交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |  
> 第二趟排序(外循环)  
> 交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |  
> 交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |  
> ②两两比较,4 > 1交换  
> 交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |  
> 交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |  
> ③两两比较,4 < 5不交换  
> 交换前状态| 2 | 1 | 4 | 5 | 6 | 9 |  
> 交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |  
> ④两两比较,5 < 6不交换  
> 交换前状态| 2 | 1 | 4 | 5 | 6 | 9 |  
> 交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |  
> 第三趟排序(外循环)  
> ①两两比较2 > 1交换  
> 交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |  
> 交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |  
> ②两两比较,2 < 4不交换  
> 交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |  
> 交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |  
> ③两两比较,4 < 5不交换  
> 交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |  
> 交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |  
> 第四趟排序(外循环)  
> 第五趟排序(外循环)  
> 排序完毕,输出最终结果1 2 4 5 6 9

import java.util.Scanner;
    
    //冒泡排序
    public class bubbleSort {
    
        public static int[] bubbleSort(int[] data){
            int len = data.length;
            int middle=0;
            for(int i = 0;i<len-1;i++)
                for(int j = 0;j<len-1-i;j++){
                    if(data[j]>data[j+1]){
                        middle=data[j];
                        data[j]=data[j+1];
                        data[j+1]=middle;
                }
            }   
            return data;
        }
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            System.out.println("请输入需要排序的数组,用逗号隔开：");
            System.out.print("排序前：");
            String inputString = sc.next();
            String[] stringArray = inputString.split(",");
            int length = stringArray.length;
            int[] data = new int[length];
            int[] data1 = new int[length];
            for(int i = 0;i<length;i++){
                data[i]=Integer.parseInt(stringArray[i]);
            }
            sc.close();
    
            data1=bubbleSort(data);
            System.out.print("排序后：");
            for(int i = 0;i<length;i++){
                if(i==length-1)
                    System.out.print(data1[i]+".");
                else
                    System.out.print(data1[i]+",");
            }
        }
    }

![这里写图片描述][SouthEast]

> 冒泡排序是一种稳定排序。

## 快速排序： ##

> 思想：  
> 1、在待排序的元素任取一个元素作为基准(通常选第一个元素)，称为基准元素；  
> 2、将待排序的元素进行分区，比基准元素大的元素放在它的右边，比其小的放在它的左边；  
> 3、对左右两个分区重复以上步骤，直到所有元素都是有序的。

![这里写图片描述][SouthEast 1]

import java.util.Scanner;
    
    public class QuickSort {
    
        //选择数组中的一个数，把数组中数字分成两部分，比该数小的移到左边，比该数大的移到右边
        public static int partition(int[] data,int start,int end){
            int pivot = 0;
            int left = start;
            int right = end;
            if( left <= right ){
                //pivot：基准元素
                pivot = data[start];
                //从左右两边交替扫描,直到left=right
                while(left!=right){
                    //从右往左扫描，找到第一个比基准元素小的元素
                    while( right > left && data[right] >= pivot)
                        right--;
                    //找到这种元素data[right]后与data[left]交换
                    data[left] = data[right];
    
                    //从左往右扫描，找到第一个比基准元素大的元素
                    while( left < right && data[left] <= pivot)
                        left++;
                    //找到这种元素data[left]后与data[right]交换
                    data[right] = data[left];
                }
            }
            data[right] = pivot;//基准元素归位
            return right;
        }
    
        public static void quickSort(int[] data,int start,int end){
            int location = 0;
            if(start < end){
                location = partition(data,start,end);
                quickSort(data,start,location-1);
                quickSort(data,location+1,end);
            }
        }
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            System.out.println("请输入需要排序的数组,用逗号隔开：");
            System.out.print("排序前：");
            String inputString = sc.next();
            String[] stringArray = inputString.split(",");
            int length = stringArray.length;
            int[] data = new int[length];
            for(int i = 0;i<length;i++){
                data[i]=Integer.parseInt(stringArray[i]);
            }
            sc.close();
    
            quickSort(data,0,length-1);
            System.out.print("排序后：");
            for(int i = 0;i<length;i++){
                if(i==length-1)
                    System.out.print(data[i]+".");
                else
                    System.out.print(data[i]+",");
            }
        }
    }

![这里写图片描述][SouthEast 2]

> 1、当分区选取的基准元素为待排序元素中的最大或最小值时，为最坏的情况，移动次数达到最大值C= 1+2+…+(n-1) = n\*(n-1)/2 = O(n^2)，最差时间复杂度为O(n^2) 。  
> 2、当分区选取的基准元素为待排序元素中的”中值”，为最好的情况，最好时间复杂度为O(nlog2n)。  
> 3、空间复杂度为O(log2n)。  
> 4、当待排序元素类似\[6,1,3,7,3\]且基准元素为6时，经过分区，形成\[1,3,3,6,7\],两个3的相对位置发生了改变，所以快速排序是一种不稳定排序。

## 选择排序 ##

> 算法思想：  
> 1、在未排序序列中找到最小（大）元素，存放到排序序列的起始位置  
> 2、再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾  
> 3、以此类推，直到所有元素均排序完毕。
> 
> 现有无序数组\[6 2 4 1 5 9\]  
> 第一趟找到最小数1,放到最前边(与首位数字交换)  
> 交换前:| 6 | 2 | 4 | 1 | 5 | 9 |  
> 交换后:| 1 | 2 | 4 | 6 | 5 | 9 |  
> 第二趟找到余下数字\[2 4 6 5 9\]里的最小数2,与当前数组的首位数字进行交换,实际没有交换,本来就在首位  
> 交换前:| 1 | 2 | 4 | 6 | 5 | 9 |  
> 交换后:| 1 | 2 | 4 | 6 | 5 | 9 |  
> 第三趟继续找到剩余\[4 6 5 9\]数字里的最小数4,实际没有交换,4待首位置无须交换  
> 第四趟从剩余的\[6 5 9\]里找到最小数5,与首位数字6交换位置  
> 交换前:| 1 | 2 | 4 | 6 | 5 | 9 |  
> 交换后:| 1 | 2 | 4 | 5 | 6 | 9 |  
> 第五趟从剩余的\[6 9\]里找到最小数6,发现它待在正确的位置,没有交换  
> 排序完毕输出正确结果\[1 2 4 5 6 9\]
> 
>  第一趟找到最小数1的细节：  
> 当前数组是| 6 | 2 | 4 | 1 | 5 | 9 |  
> 先把6取出来,让它扮演最小数  
> 当前最小数6与其它数一一进行比较,发现更小数就交换角色  
> 当前最小数6与2比较,发现更小数,交换角色,此时最小数是2,接下来2与剩余数字比较  
> 当前最小数2与4比较,不动  
> 当前最小数2与1比较,发现更小数,交换角色,此时最小数是1,接下来1与剩余数字比较  
> 当前最小数1与5比较,不动  
> 当前最小数1与9比较,不动,到达末尾  
> 当前最小数1与当前首位数字进行位置交换,如下所示  
> 交换前:| 6 | 2 | 4 | 1 | 5 | 9 |  
> 交换后:| 1 | 2 | 4 | 6 | 5 | 9 |  
> 完成一趟排序,其余步骤类似

import java.util.Scanner;
    
    public class selectionSort {
    
        public static void selection_sort(int[] arr) {
            int min,temp;
    
            //i:未排序序列的首位
            for(int i = 0 ; i <arr.length-1;i++){
                //找出最小数，与首位交换
                min = i;
                for(int j = i+1 ;j<arr.length;j++){
                    if(arr[min]>arr[j])
                        min = j ;
                    //把最小值跟未排序序列的首位交换
                    temp = arr[min];
                    arr[min] = arr[i];
                    arr[i] = temp;
                }
            }
        }
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            System.out.println("请输入需要排序的数组,用逗号隔开：");
            System.out.print("排序前：");
            String inputString = sc.next();
            String[] stringArray = inputString.split(",");
            int length = stringArray.length;
            int[] data = new int[length];
            for(int i = 0;i<length;i++){
                data[i]=Integer.parseInt(stringArray[i]);
            }
            sc.close();
    
            selection_sort(data);
            System.out.print("排序后：");
            for(int i = 0;i<length;i++){
                if(i==length-1)
                    System.out.print(data[i]+".");
                else
                    System.out.print(data[i]+",");
            }
        }
    }

![这里写图片描述][SouthEast 3]

>  选择排序是不稳定排序

## 插入排序 ##

> 1、从第一个元素开始，该元素可以认为已经被排序  
> 2、取出下一个元素，在已经排序的元素序列中从后向前扫描  
> 3、如果该元素（已排序）大于新元素，将该元素移到下一位置  
> 4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置  
> 5、将新元素插入到该位置后重复步骤2~5

输入数组： \[5, 6, 3, 1, 8, 7, 2, 4\]  
![这里写图片描述][SouthEast 4]

import java.util.Scanner;
    
    public class insertionSort {
    
        public static void InsertionSort(int[] data){
            int length = data.length;
            for(int i = 0; i < length-1 ; i++ )
                for(int j = i+1 ; j > 0 ; j-- )
                    if(data[j-1]>data[j]){
                        int temp = data[j];
                        data[j] = data[j-1];
                        data[j-1] = temp;
                    }
        }
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            System.out.println("请输入需要排序的数组,用逗号隔开：");
            System.out.print("排序前：");
            String inputString = sc.next();
            String[] stringArray = inputString.split(",");
            int length = stringArray.length;
            int[] data = new int[length];
            for(int i = 0;i<length;i++){
                data[i]=Integer.parseInt(stringArray[i]);
            }
            sc.close();
    
            InsertionSort(data);
    
            System.out.print("排序后：");
            for(int i = 0;i<length;i++){
                if(i==length-1)
                    System.out.print(data[i]+".");
                else
                    System.out.print(data[i]+",");
            }
        }
    }

![这里写图片描述][SouthEast 5]

>  插入排序是稳定排序

## 归并排序 ##

> 1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列  
> 2、设定两个指针，最初位置分别为两个已经排序序列的起始位置  
> 3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置  
> 4、重复步骤3直到某一指针达到序列尾  
> 5、将另一序列剩下的所有元素直接复制到合并序列尾

![这里写图片描述][SouthEast 6]

import java.util.Scanner;
    
    public class MergeSort {
        
    
        //归并排序
        public static void mergeSort(int[] data){
            int[] temp =new int[data.length];
            sort(data,temp,0,data.length-1);
        }
    
        /** 
         * 递归分治 
         * @param data1 待排数组
         * @param data2 临时数组，大小和data1相同
         * @param left 左指针
         * @param right 右指针 
         */
        public static void sort(int[] data1, int[] data2,int left, int right) {
            if(left < right){
                // 找出中间索引 
                int mid = (left+right)/2;
                sort(data1,data2,left,mid);// 对左边数组进行递归  
                sort(data1,data2,mid+1,right);// 对右边数组进行递归  
                merge(data1,data2,left,mid,right);//合并
            }
        }
    
        //合并两个有序的数组
        public static void merge(int data[],int temp[], int left, int mid, int right) {
            //[left,mid] [mid+1,right]
            int i = left ;
            int j = mid + 1 ;
            int k = 0 ;
             从两个数组中取出最小的放入临时temp数组
            while(i <= mid && j <= right){
                if(data[i]<=data[j])
                    temp[k++] = data[i++];
                else
                    temp[k++] = data[j++];
            }
            // 剩余部分依次放入temp数组（实际上两个while只会执行其中一个）
            //当某个数组里只剩1个元素时，直接复制
            while(i<=mid)
                temp[k++] = data[i++];
            while(j<=right)
                temp[k++] = data[j++];
    
            //将临时数组中的内容拷贝回原数组中
            for(i=0;i<k;i++){
                data[left+i] = temp[i];
            }
        }
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            System.out.println("请输入需要排序的数组,用逗号隔开：");
            System.out.print("排序前：");
            String inputString = sc.next();
            String[] stringArray = inputString.split(",");
            int length = stringArray.length;
            int[] data = new int[length];
            for(int i = 0;i<length;i++){
                data[i]=Integer.parseInt(stringArray[i]);
            }
            sc.close();
    
            mergeSort(data);
    
            System.out.print("排序后：");
            for(int i = 0;i<length;i++){
                if(i==length-1)
                    System.out.print(data[i]+".");
                else
                    System.out.print(data[i]+",");
            }
        }
    }

![这里写图片描述][SouthEast 7]

>  归并排序是稳定排序

## 排序算法比较 ##

![这里写图片描述][SouthEast 8]

冒泡排序：  
优点：稳定  
缺点：慢，每次只能移动相邻两个数据

选择排序：  
优点：移动数据的次数已知  
缺点：不稳定，且比较次数多

插入排序：  
优点：稳定，快  
缺点：比较的次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。

快速排序：  
优点：极快，数据移动少  
缺点：不稳定

归并排序：  
优点：稳定，时间复杂度低  
缺点：空间复杂度略高，需要O(n)辅助空间

[SouthEast]: /images/20220613/911f4c2485114fbc95a06194b78e43b9.png
[SouthEast 1]: /images/20220613/4296135ca9454c8ebb48e31c1ac3bc46.png
[SouthEast 2]: /images/20220613/277450f3a15e49148777421be7c97c61.png
[SouthEast 3]: /images/20220613/d5dc2e5e73354fe1bf7ee535d1125f71.png
[SouthEast 4]: /images/20220613/3ecdd8083f334012a4b9513664aeacc0.png
[SouthEast 5]: /images/20220613/8421f8b53c284d0883bf8a5f4ea1aad7.png
[SouthEast 6]: /images/20220613/03f97e5f2a404caf8884e3a52c3a5577.png
[SouthEast 7]: /images/20220613/bd506a317a6a43b4b2219266b1bcfa9b.png
[SouthEast 8]: /images/20220613/a1711e7c12304d2488631ec936f1fcb3.png