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

我会带着你远行 2022-06-13 07:11 283阅读 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

  1. import java.util.Scanner;
  3. //冒泡排序
  4. public class bubbleSort {
  6.     public static int[] bubbleSort(int[] data){
  7.         int len = data.length;
  8.         int middle=0;
  9.         for(int i = 0;i<len-1;i++)
  10.             for(int j = 0;j<len-1-i;j++){
  11.                 if(data[j]>data[j+1]){
  12.                     middle=data[j];
  13.                     data[j]=data[j+1];
  14.                     data[j+1]=middle;
  15.             }
  16.         }   
  17.         return data;
  18.     }
  20.     public static void main(String[] args) {
  21.         Scanner sc = new Scanner(System.in);
  22.         System.out.println("请输入需要排序的数组,用逗号隔开：");
  23.         System.out.print("排序前：");
  24.         String inputString = sc.next();
  25.         String[] stringArray = inputString.split(",");
  26.         int length = stringArray.length;
  27.         int[] data = new int[length];
  28.         int[] data1 = new int[length];
  29.         for(int i = 0;i<length;i++){
  30.             data[i]=Integer.parseInt(stringArray[i]);
  31.         }
  32.         sc.close();
  34.         data1=bubbleSort(data);
  35.         System.out.print("排序后：");
  36.         for(int i = 0;i<length;i++){
  37.             if(i==length-1)
  38.                 System.out.print(data1[i]+".");
  39.             else
  40.                 System.out.print(data1[i]+",");
  41.         }
  42.     }
  43. }

这里写图片描述

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

快速排序：

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

这里写图片描述

  1. import java.util.Scanner;
  3. public class QuickSort {
  5.     //选择数组中的一个数，把数组中数字分成两部分，比该数小的移到左边，比该数大的移到右边
  6.     public static int partition(int[] data,int start,int end){
  7.         int pivot = 0;
  8.         int left = start;
  9.         int right = end;
  10.         if( left <= right ){
  11.             //pivot：基准元素
  12.             pivot = data[start];
  13.             //从左右两边交替扫描,直到left=right
  14.             while(left!=right){
  15.                 //从右往左扫描，找到第一个比基准元素小的元素
  16.                 while( right > left && data[right] >= pivot)
  17.                     right--;
  18.                 //找到这种元素data[right]后与data[left]交换
  19.                 data[left] = data[right];
  21.                 //从左往右扫描，找到第一个比基准元素大的元素
  22.                 while( left < right && data[left] <= pivot)
  23.                     left++;
  24.                 //找到这种元素data[left]后与data[right]交换
  25.                 data[right] = data[left];
  26.             }
  27.         }
  28.         data[right] = pivot;//基准元素归位
  29.         return right;
  30.     }
  32.     public static void quickSort(int[] data,int start,int end){
  33.         int location = 0;
  34.         if(start < end){
  35.             location = partition(data,start,end);
  36.             quickSort(data,start,location-1);
  37.             quickSort(data,location+1,end);
  38.         }
  39.     }
  41.     public static void main(String[] args) {
  42.         Scanner sc = new Scanner(System.in);
  43.         System.out.println("请输入需要排序的数组,用逗号隔开：");
  44.         System.out.print("排序前：");
  45.         String inputString = sc.next();
  46.         String[] stringArray = inputString.split(",");
  47.         int length = stringArray.length;
  48.         int[] data = new int[length];
  49.         for(int i = 0;i<length;i++){
  50.             data[i]=Integer.parseInt(stringArray[i]);
  51.         }
  52.         sc.close();
  54.         quickSort(data,0,length-1);
  55.         System.out.print("排序后：");
  56.         for(int i = 0;i<length;i++){
  57.             if(i==length-1)
  58.                 System.out.print(data[i]+".");
  59.             else
  60.                 System.out.print(data[i]+",");
  61.         }
  62.     }
  63. }

这里写图片描述

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 |
完成一趟排序,其余步骤类似

  1. import java.util.Scanner;
  3. public class selectionSort {
  5.     public static void selection_sort(int[] arr) {
  6.         int min,temp;
  8.         //i:未排序序列的首位
  9.         for(int i = 0 ; i <arr.length-1;i++){
  10.             //找出最小数，与首位交换
  11.             min = i;
  12.             for(int j = i+1 ;j<arr.length;j++){
  13.                 if(arr[min]>arr[j])
  14.                     min = j ;
  15.                 //把最小值跟未排序序列的首位交换
  16.                 temp = arr[min];
  17.                 arr[min] = arr[i];
  18.                 arr[i] = temp;
  19.             }
  20.         }
  21.     }
  23.     public static void main(String[] args) {
  24.         Scanner sc = new Scanner(System.in);
  25.         System.out.println("请输入需要排序的数组,用逗号隔开：");
  26.         System.out.print("排序前：");
  27.         String inputString = sc.next();
  28.         String[] stringArray = inputString.split(",");
  29.         int length = stringArray.length;
  30.         int[] data = new int[length];
  31.         for(int i = 0;i<length;i++){
  32.             data[i]=Integer.parseInt(stringArray[i]);
  33.         }
  34.         sc.close();
  36.         selection_sort(data);
  37.         System.out.print("排序后：");
  38.         for(int i = 0;i<length;i++){
  39.             if(i==length-1)
  40.                 System.out.print(data[i]+".");
  41.             else
  42.                 System.out.print(data[i]+",");
  43.         }
  44.     }
  45. }

这里写图片描述

选择排序是不稳定排序

插入排序

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

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

  1. import java.util.Scanner;
  3. public class insertionSort {
  5.     public static void InsertionSort(int[] data){
  6.         int length = data.length;
  7.         for(int i = 0; i < length-1 ; i++ )
  8.             for(int j = i+1 ; j > 0 ; j-- )
  9.                 if(data[j-1]>data[j]){
  10.                     int temp = data[j];
  11.                     data[j] = data[j-1];
  12.                     data[j-1] = temp;
  13.                 }
  14.     }
  16.     public static void main(String[] args) {
  17.         Scanner sc = new Scanner(System.in);
  18.         System.out.println("请输入需要排序的数组,用逗号隔开：");
  19.         System.out.print("排序前：");
  20.         String inputString = sc.next();
  21.         String[] stringArray = inputString.split(",");
  22.         int length = stringArray.length;
  23.         int[] data = new int[length];
  24.         for(int i = 0;i<length;i++){
  25.             data[i]=Integer.parseInt(stringArray[i]);
  26.         }
  27.         sc.close();
  29.         InsertionSort(data);
  31.         System.out.print("排序后：");
  32.         for(int i = 0;i<length;i++){
  33.             if(i==length-1)
  34.                 System.out.print(data[i]+".");
  35.             else
  36.                 System.out.print(data[i]+",");
  37.         }
  38.     }
  39. }

这里写图片描述

插入排序是稳定排序

归并排序

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

这里写图片描述

  1. import java.util.Scanner;
  3. public class MergeSort {
  6.     //归并排序
  7.     public static void mergeSort(int[] data){
  8.         int[] temp =new int[data.length];
  9.         sort(data,temp,0,data.length-1);
  10.     }
  12.     /** 
  13.      * 递归分治 
  14.      * @param data1 待排数组
  15.      * @param data2 临时数组，大小和data1相同
  16.      * @param left 左指针
  17.      * @param right 右指针 
  18.      */
  19.     public static void sort(int[] data1, int[] data2,int left, int right) {
  20.         if(left < right){
  21.             // 找出中间索引 
  22.             int mid = (left+right)/2;
  23.             sort(data1,data2,left,mid);// 对左边数组进行递归  
  24.             sort(data1,data2,mid+1,right);// 对右边数组进行递归  
  25.             merge(data1,data2,left,mid,right);//合并
  26.         }
  27.     }
  29.     //合并两个有序的数组
  30.     public static void merge(int data[],int temp[], int left, int mid, int right) {
  31.         //[left,mid] [mid+1,right]
  32.         int i = left ;
  33.         int j = mid + 1 ;
  34.         int k = 0 ;
  35.          从两个数组中取出最小的放入临时temp数组
  36.         while(i <= mid && j <= right){
  37.             if(data[i]<=data[j])
  38.                 temp[k++] = data[i++];
  39.             else
  40.                 temp[k++] = data[j++];
  41.         }
  42.         // 剩余部分依次放入temp数组（实际上两个while只会执行其中一个）
  43.         //当某个数组里只剩1个元素时，直接复制
  44.         while(i<=mid)
  45.             temp[k++] = data[i++];
  46.         while(j<=right)
  47.             temp[k++] = data[j++];
  49.         //将临时数组中的内容拷贝回原数组中
  50.         for(i=0;i<k;i++){
  51.             data[left+i] = temp[i];
  52.         }
  53.     }
  55.     public static void main(String[] args) {
  56.         Scanner sc = new Scanner(System.in);
  57.         System.out.println("请输入需要排序的数组,用逗号隔开：");
  58.         System.out.print("排序前：");
  59.         String inputString = sc.next();
  60.         String[] stringArray = inputString.split(",");
  61.         int length = stringArray.length;
  62.         int[] data = new int[length];
  63.         for(int i = 0;i<length;i++){
  64.             data[i]=Integer.parseInt(stringArray[i]);
  65.         }
  66.         sc.close();
  68.         mergeSort(data);
  70.         System.out.print("排序后：");
  71.         for(int i = 0;i<length;i++){
  72.             if(i==length-1)
  73.                 System.out.print(data[i]+".");
  74.             else
  75.                 System.out.print(data[i]+",");
  76.         }
  77.     }
  78. }

这里写图片描述

归并排序是稳定排序

排序算法比较

这里写图片描述

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

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

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

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

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

发表评论

表情：
评论列表 （有 0 条评论，283人围观）

还没有评论，来说两句吧...

相关阅读