devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

七大经典排序算法(动图演示+代码展示)_七大经典排序算法动态图

作者：从前慢现在也慢 | 2024-02-29 05:44:21

赞

踩

七大经典排序算法动态图

常见排序算法可以分为两大类：
非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。
线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。  
   

算法复杂度 

 

1. 冒泡排序(BubbleSort)

冒泡排序是一种简单的排序算法，是一种减治算法的应用,通过重复走过要排序的数组，每一次比较两个相邻元素的大小，如果后一个元素比前一个元素小就交换过来，最终完成排序，这种算法的命名也是由最小的元素总是会慢慢从最后“浮”到前面来而得名 (每次从无序区间取一个数去无序区间遍历)

步骤：

  • 从第一组两个相邻元素开始比较，依次往后交换
  • 每经过一次排序较大的元素就会被放到后面，直到最大的元素被放到最后，那么下一次排序的时候也就不用用它（最后一个数）和它相邻的前面的数进行比较了，最后的元素就成了“稳定元素”
  • 重复以上步骤，每一次排序完成，最后的“稳定元素”都会增加一个，直到没有可以交换的元素，那么排序就完成了

 动态图演示：

 代码展示

  1. package com;
  2.  
  3. import java.util.Arrays;
  4.  
  5. /**
  6.  * package:com
  7.  * Description:bubbleSort
  8.  * @date:2019/4/27
  9.  * @Author:weiwei
  10.  **/
  11. public class bubbleSort {
  12.     /**
  13.      * 双层循环遍历数组
  14.      * 第一层循环表示循环次数,一次循环解决一个数的问题,一共需要array.length次
  15.      *       更优化的方式是array.length-1次(最后一个数不需要比较)
  16.      * 第二层比较相邻两个数的大小,共需要array.length-2-i次(i是循环到哪个数,2是最后一个数不用比较
  17.      *       下标从 0 开始,所以是减二
  18.      * @param array
  19.      * @return
  20.      */
  21.     private static int[] bubbleSort(int [] array){
  22.         for(int i = 0;i<array.length;i++){
  23.             for(int j = 0;j <= array.length -2-i;j++){
  24.  
  25.                 if(array[j] > array[j+1]){
  26.                     int temp = array[j];
  27.                     array[j] = array[j+1];
  28.                     array[j+1] = temp;
  29.                 }
  30.             }
  31.         }
  32.         return array;
  33.     }
  34.     public static void main(String[] args) {
  35.         int[] array = {9,2,4,7,5,8,1,3,6};
  36.         System.out.println(Arrays.toString(bubbleSort(array)));
  37.  
  38.     }
  39. }

2.选择排序(SelectionSort)

选择排序是一种简单直观的排序算法,是减治算法的应用,对数据不敏感,原理是:

   首先在未排序序列中找到最小元素,存放到排列序列的起始位置,然后在剩余未排序元素中继续寻找最小元素,然后放到已经排好序序列的末尾,以此类推,直到所有元素均排序完毕

步骤:

  • 把要排序的序列分为有序序列和无序序列
  • 遍历序列,每一次从无序序列找到最小元素,定义为minIndex=i,放到无序序列最前面,
  • 直到无序区间内没有元素,也就是所有元素都排好序

动图演示:

代码展示: 

  1. package Sort;
  2.  
  3. import java.util.Arrays;
  4.  
  5. /**
  6.  * Author:weiwei
  7.  * description:
  8.  * Creat:2019/5/2
  9.  **/
  10. public class SelectSort {
  11.  
  12.     private static int[] SelectSort(int[] array) {
  13.         for (int i = 0; i < array.length; i++) {
  14.             int min = i;
  15.             for (int j = i+1; j < array.length; j++) {
  16.                 if (array[j] < array[min]) {
  17.                     min = j;
  18.                 }
  19.             }
  20.             int t = array[min];
  21.             array[min] = array[i];
  22.             array[i] = t;
  23.  
  24.         }
  25.         return array;
  26.     }
  27.  
  28.     public static void main(String[] args) {
  29.         int[] array = {8,3,7,1,4,6,2,9,5};
  30.         System.out.println(Arrays.toString(SelectSort(array)));
  31.     }
  32. }

3.插入排序(Insertion Sort)

插入排序是一种简单直观的排序算法,是减治算法的应用,原理是:通过构建有序数列,对于未排序数据,在已排序序列中,从后往前扫描,找到对应位置并插入(每次从无序区间取一个数到有序区间去遍历,找到插入的位置)

步骤:

  • 从第一个元素开始,认为第一个元素已经被排序
  • 取出下一个元素,在已排好序的序列中从后往前扫描
  • 如果该元素(已排好序)大于新元素,将该元素移到下一位置
  • 重复步骤3,直到找到已排好序的元素小于或者等于新元素的位置
  • 将新元素插入到该位置后
  • 重复步骤2-5

动图演示:

代码展示:

  1. package Sort;
  2.  
  3. import java.util.Arrays;
  4.  
  5. /**
  6.  * Author:weiwei
  7.  * description:
  8.  * Creat:2019/5/3
  9.  **/
  10. public class insertSort {
  11.  
  12.     /**遍历查找
  13.      *先查找
  14.      *再搬
  15.      * @param array
  16.      */
  17.     private static void insertSort1(int[] array){
  18.         for(int i =0;i<array.length;i++){
  19.             //有序[0,i)
  20.             //无序[i,array.length)
  21.             //1.在有序区间遍历查找,从后往前查找
  22.             int j;
  23.             for(j=i-1;j >= 0 &&array[i] < array[j];j--){
  24.             }
  25.             //j+1就是要插入的位置
  26.             //插入数据,从后往前搬数据
  27.             int pos = j+1;
  28.             int key = array[i];
  29.             for( int k = i;k>pos;k--){
  30.                 array[k] = array[k-1];
  31.             }
  32.             array[pos] = key;
  33.         }
  34.     }
  35.  
  36.     /**遍历查找
  37.      * 边查找边搬
  38.      * @param array
  39.      */
  40.     private static int[] insertSort2(int[] array){
  41.         int len = array.length;
  42.         int preIndex,current;
  43.         for(int i = 0;i<len;i++){
  44.             preIndex = i-1;
  45.             current = array[i];
  46.  
  47.             while(preIndex >= 0 && array[preIndex] > current ){
  48.                 array[preIndex+1] = array[preIndex];
  49.                 preIndex--;
  50.             }
  51.             array[preIndex+1] = current;
  52.         }
  53.         return array;
  54.     }
  55.  
  56.     /**
  57.      * 二分查找(重点)
  58.      * @param array
  59.      */
  60.     private static void insertSort3(int[] array){
  61.         for(int i = 0;i<array.length;i++){
  62.             int key = array[i];
  63.             //[0,i)
  64.             int left = 0;
  65.             int right = i;
  66.  
  67.             while(left < right){
  68.                 int mid = left + (left - right)/2;
  69.                 if(key == array[mid]){
  70.                     left = mid + 1;
  71.                 }else if(key < array[mid]){
  72.                     right = mid;
  73.                 }else{
  74.                     left = mid +1;
  75.                 }
  76.             }
  77.             int pos = left;
  78.             for (int k = i;k>pos;k--){
  79.                 array[k] = array[k-1];
  80.             }
  81.             array[pos] = key;
  82.         }
  83.     }
  84.  
  85.     public static void main(String[] args) {
  86.         int[] array = {9,2,7,4,5,3,1,8,6,5};
  87.         insertSort1(array);
  88.         System.out.println(Arrays.toString(array));
  89.     }
  90. }

 4.希尔排序（shell sort）

希尔排序是第一个突破O(n^2)的排序算法，是简单插入排序的改进法， 它与插入排序不同之处在于，它会提前做一个预排序,给序列分组预排序,也叫做分组插排,分的组越多越接近有序

动图演示：

                    

代码展示：

  1. package Sort;
  2.  
  3. import java.util.Arrays;
  4.  
  5. /**
  6.  * Author:weiwei
  7.  * description:希尔排序
  8.  * Creat:2019/5/3
  9.  **/
  10. public class insertSortWithGap {
  11.  
  12.     private static void insertSortWithGap(int[] array, int gap) {
  13.         for (int i = 0; i < array.length; i++) {
  14.             int key = array[i];
  15.             int j = i - gap;
  16.             for (; j >= 0 && key < array[j]; j = j - gap) {
  17.                 array[j + gap] = array[j];
  18.             }
  19.             array[j + gap] = key;
  20.         }
  21.     }
  22.  
  23.     /**
  24.      * 时间复杂度:
  25.      * 最好情况:O(n)
  26.      * 最坏情况:O(n^2)   比插排最坏情况的概率变小了
  27.      * 平均情况:O(n^1.2 - 1.3)
  28.      * 空间复杂度:O(1)
  29.      * 稳定性:不稳定
  30.      *
  31.      * @param array
  32.      */
  33.     private static int[] shellSort(int[] array) {
  34.         int gap = array.length;
  35.         while (true) {
  36.             //gap = gap /2;
  37.             gap = (gap / 3) + 1;
  38.  
  39.             insertSortWithGap(array, gap);
  40.  
  41.             if (gap == 1) {
  42.                 break;
  43.             }
  44.         }
  45.         return array;
  46.     }
  47.  
  48.     public static void main(String[] args) {
  49.         int [] array = {9,3,1,4,7,2,8,6,5};
  50.         System.out.println(Arrays.toString(shellSort(array)));
  51.     }
  52. }

 5.归并排序（Merge sort）

归并排序是建立在一种建立在归并算法上一种有效的排序方法，该方法是采用分治算法的一个典型的应用，对数据不敏感,将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列间有序，算法复杂度为(nlogn)

算法描述：

1.把长度为n的序列分为两个长度为n/2的子序列

2.对这两个子序列分别归并排序

3.将两个排序好的子序列合并成一个最终的有序序列

动图演示：

代码展示：

  1. package Sort;
  2.  
  3. import java.util.Arrays;
  4.  
  5. /**
  6.  * Author:weiwei
  7.  * description:归并排序(递归方式)
  8.  * Creat:2019/4/27
  9.  **/
  10. public class MergeSort {
  11.     private static void merge(int[] array,int low,int mid,int high,int[] extra){
  12.         int i = low;  //遍历[low,mid]
  13.         int j = mid;  //遍历[mid,high]
  14.         int x = 0;    //遍历extra
  15.  
  16.         while(i < mid && j < high){
  17.              if(array[i] <= array[j]){
  18.                  extra[x++] = array[i++];
  19.              }else{
  20.                  extra[x++] = array[j++];
  21.              }
  22.         }
  23.         while(i < mid){
  24.             extra[x++] = array[i++];
  25.         }
  26.         while(j < high){
  27.             extra[x++] = array[j++];
  28.         }
  29.         for(int k = low;k < high;k++){
  30.             array[k] = extra[k - low];
  31.         }
  32.     }
  33.     private static void mergeSortInner(int[] array,int low,int high,int[] extra){
  34.         if (low == high - 1){
  35.             return;
  36.         }
  37.         if(low >= high){
  38.             return;
  39.         }
  40.  
  41.         //平均切分
  42.         int mid = low + (high - low)/2;
  43.         //[low,mid)+[mid,high)
  44.         //2.分治算法处理两个小区间
  45.         mergeSortInner(array,low,mid,extra);
  46.         mergeSortInner(array,mid,high,extra);
  47.  
  48.         //左右两个小区间已经有序了
  49.         merge(array,low,mid,high,extra);
  50.     }
  51.  
  52.     private static void mergeSort(int[] array) {
  53.         int[] extra = new int [array.length];//设定长度,避免造成空间浪费
  54.         mergeSortInner(array,0,array.length,extra);
  55.     }
  56.  
  57.     //非递归方式
  58.     private static void mergeNoR(int[] array){
  59.         int[] extra = new int [array.length];
  60.         for(int i = 1;i<array.length;i *= 2){
  61.             for(int j =0;j<array.length;j +=2 * i){
  62.                 int low = j;
  63.                 int mid = low + i;
  64.                 if( mid >= array.length){
  65.                     continue;
  66.                 }
  67.                 int high = mid + i;
  68.                 if(high > array.length){
  69.                     high = array.length;
  70.                 }
  71.                 merge(array,low,mid,high,extra);
  72.             }
  73.         }
  74.     }
  75.  
  76.     public static void main(String[] args) {
  77.         int[] array1 = {9,3,1,5,4,2,7,6,8};
  78.         int[] array2 = {8,3,1,2,5,3,7,6,2};
  79.         mergeSort(array1);
  80.         mergeNoR(array2);
  81.         System.out.println(Arrays.toString(array1));
  82.         System.out.println(Arrays.toString(array2));
  83.     }
  84. }

6.快速排序(Quick Sort)

  快速排序的基本思想：

        在要排序的序列中选择一个基准值(通常选择最右边的值为基准值),然后遍历整个序列,每个数都和基准值进行比较,并且发生一定的交换,遍历结束后使得比基准值小的数(包括等于)都在基准值的左边,比基准值大的数(包括等于)都在基准值的右边,然后采用分治算法的思想,分别对两个小的区间进行同样的方式处理,直到区间的size=0或者=1,就说明序列已经有序了,快速排序完成

算法描述:

快速排序使用分治算法来把一个序列分为两个子序列,具体算法描述如下：

   1. 从序列中选择最右边的数作为基准,称为 “基准值”（pivot）；

      
   2. 遍历排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一               边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

           
   3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

快速排序的步骤:

  1.选择基准值(选择基准值有三个方法)

  • 选择最边上作为基准值(左右都可以)
  • 随机法(random.nextInt())
  • 三数取中法[对于第二三中方法,确定基准值后,将基准值交换到最边上]      

2.分割(partition操作),比基准值 <= 在基准值左边,比基准值 >= 在基准值右边,partition操作也有三种方法:

  • Hover法(左右遍历)
  • 挖坑法(左右遍历)
  • 前后下标法(前后遍历)

3. 用分治法处理左右两个小区间,直到区间的size == 1(已经有序)或者 size == 0,则停止排序 动态图展示: 

代码展示:

快速排序

  1. package Sort;
  2.  
  3. import java.util.Arrays;
  4.  
  5. /**
  6.  * Author:weiwei
  7.  * description:快速排序
  8.  * Creat:2019/4/27
  9.  **/
  10. public class QuickSort {
  11.  
  12.     private static void swap(int[] array,int i,int j){
  13.         int t = array[i];
  14.         array[i] = array[j];
  15.         array[j] = t;
  16.     }
  17.  
  18.     private static int  partition1(int[] array,int left,int right){
  19.         int begin = left;
  20.         int end = right;
  21.         int pivot = array[right];
  22.         while(begin < end){
  23.             while( begin < end && array[begin] <= pivot){
  24.                 begin++;  //当前数比基准值小,就往后遍历,遇到比基准值大的数才停下来
  25.             }
  26.             while(begin < end && array[end] >= pivot){
  27.                 end--;    //当前数比基准值大,就往前遍历,遇到比基准值小的数才停下来
  28.             }
  29.             swap(array,begin,end); //否则,遍历无法继续,交换所指向的值,再继续遍历
  30.         }
  31.         swap(array,begin,right);  //遍历到最后begin == end,将right的值与begin的值交换
  32.         return begin;             //此时,序列中基准值左边所有的值就比基准值小,右边的数就比基准值大
  33.  
  34.     }
  35. private static void quickSortInner(int[] array,int left,int right){
  36.         if(left > right){
  37.             //size == 1 已经有序
  38.             return;
  39.         }
  40.         if(left == right){
  41.             //size == 0
  42.             return;
  43.         }
  44.         int originIndex = medianofthree(array,left,right);
  45.         swap(array,originIndex,right);
  46.  
  47.         //要排序的区间是array[left,right]
  48.         //1.找基准值 array[right]
  49.         //2.遍历整个区间,把区间的为三部分
  50.         int pivotIndex = partition1(array,left,right);
  51.         //3.分治算法
  52.         //用相同的方式处理两个小区间,直到size == 1 | size == 0
  53.         //比基准值小的区间[left,pivotIndex-1]
  54.         quickSortInner(array,left,pivotIndex-1);
  55.         //比基准值大的区间[pivotIndex+1,right]
  56.         quickSortInner(array,pivotIndex+1,right);
  57.     }
  58.     private static void  quickSort(int[] array){
  59.         quickSortInner(array,0,array.length -1);
  60.     }
  61.  
  62.     public static void main(String[] args) {
  63.         int[] array = {9,3,1,5,4,2,7,6,8};
  64.         quickSort(array);
  65.         System.out.println(Arrays.toString(array));
  66.     }
  67. }

 用Hover方法进行partition操作

  1. //Hover法做partition操作
  2.     private static int  partition1(int[] array,int left,int right){
  3.         int begin = left;
  4.         int end = right;
  5.         int pivot = array[right];
  6.         while(begin < end){
  7.             while( begin < end && array[begin] <= pivot){
  8.                 begin++;  //当前数比基准值小,就往后遍历,遇到比基准值大的数才停下来
  9.             }
  10.             while(begin < end && array[end] >= pivot){
  11.                 end--;    //当前数比基准值大,就往前遍历,遇到比基准值小的数才停下来
  12.             }
  13.             swap(array,begin,end); //否则,遍历无法继续,交换所指向的值,再继续遍历
  14.         }
  15.         swap(array,begin,right);  //遍历到最后begin == end,将right的值与begin的值交换
  16.         return begin;             //此时,序列中基准值左边所有的值就比基准值小,右边的数就比基准值大
  17.  
  18.     }

用挖坑法做partition操作

  1. //用挖坑法做partition操作
  2.     private static int partition2(int[] array,int left,int right){
  3.         int begin = left;
  4.         int end = right;
  5.         int pivot = array[right];
  6.         while(begin < end){
  7.             while(begin < end && array[begin] <= pivot){
  8.                 begin++;   //当前数比基准值小,就往后遍历,遇到比基准值大的数才停下来
  9.             }
  10.             array[begin] = array[end];  //否则,将end的值赋给begin
  11.             while(begin < end && array[begin] <= pivot){
  12.                 end--;    //当前数比基准值大,就往前遍历,遇到比基准值小的数才停下来
  13.             }
  14.             array[end] = array[begin]; //否则,将begin的值赋给end
  15.         }
  16.         array[begin] = pivot;  //最终begin == end时,将pivot的值赋给begin
  17.         return begin;
  18.     }

 用前后遍历的方法partition操作

  1. //前后下标法做partition操作
  2.     private static int parttiton3(int[] array,int left,int right){
  3.         int d = left;
  4.         for(int i = left;i<right;i++){
  5.             if(array[i] < array[right]){
  6.                 swap(array,d,i);
  7.                 d++;
  8.             }
  9.         }
  10.         swap(array,d,right);
  11.         return d;
  12.     }

选择基准的方法:三数取中法

  1. //三数取中
  2.     private static int medianofthree(int[] array,int left,int right) {
  3.         int mid = left + (right - left) / 2;
  4.         if (array[left] > array[right]) {
  5.             if (array[left] < array[mid]) {
  6.                 return left;
  7.             } else if (array[mid] > array[right]) {
  8.                 return mid;
  9.             } else {
  10.                 return right;
  11.             }
  12.         } else {
  13.             if (array[right] < array[mid]) {
  14.                 return right;
  15.             } else if (array[mid] > array[left]) {
  16.                 return mid;
  17.             } else {
  18.                 return left;
  19.             }
  20.         }
  21.     }

7. 堆排序(Heap Sort)

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。是减治算法的应用,对数据不敏感,堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

 算法描述

     1. 将初始待排序关键字序列构建成大堆，此堆为初始的无序区；
     2. 选择最大的元素(堆顶元素)放到无序序列最后面，此时得到新的无序区和新的有序区,每次在无序序列中选择最大的的元素放到无序序列最后面,
     3. 直到最后叶子结点,不再向下调整,堆排序完成
动态图演示:

                                      

代码展示:

  1. package com.bittech;
  2.  
  3. /**
  4.  * Author:weiwei
  5.  * description:堆排序
  6.  * Creat:2019/4/27
  7.  **/
  8. public class heapSort {
  9.  
  10.     private static void heapify(int[] array,int size,int index){
  11.         //判断index是不是叶子结点
  12.         while(2*index+1 < size){
  13.             //找到最大孩子的下标
  14.             int max = 2 * index + 1;
  15.             if(max + 1 <size && array[max+1] > array[max]){
  16.                 max = 2 * index + 2;
  17.             }
  18.  
  19.             //3.判断最大得孩子和根的值
  20.             if(array[index] < array[max]){
  21.                 swap(array,index,max);
  22.  
  23.                 index = max;
  24.             }else{
  25.                 //根的值比较大,不需要交换,可以直接退出了
  26.                 break;
  27.             }
  28.         }
  29.     }
  30.     private static void createHeap(int[] array){
  31.         //[从最后一个非叶子节点的下标,根]  向下调整
  32.         //[(array.length-2)/2,0]
  33.         for(int i = (array.length-2/2);i>=0;i--){
  34.             heapify(array,array.length,i);
  35.         }
  36.     }
  37.     private static void swap(int[] array,int i,int j){
  38.         int t =array[i];
  39.         array[i] = array[j];
  40.         array[j] = t;
  41.  
  42.     }
  43.     private static void heapSort(int[] array){
  44.         //建堆  大堆
  45.         createHeap(array);
  46.  
  47.         //减治处理
  48.         for(int i =0;i<array.length;i++){
  49.             //有序[length - i,length]
  50.             //无序[0,length - i - 1]
  51.             //最大的数在[0],最大的数应该放到的下标是
  52.             //[length-i-1]
  53.             swap(array,0,array.length -1-i);
  54.             //处理[0]无序剩余部分满足堆的性质
  55.             //无序[0,length-i-2]
  56.             //有序[length-i-1,length]
  57.             //size剩余无序部分的长度
  58.             heapify(array,array.length-1-i,0);
  59.         }
  60.     }
  61.  
  62.     public static void main(String[] args) {
  63.         int[] array = { 9, 5, 2, 7, 3, 6, 8, 8, 4, 9, 3, 1, 2 };
  64.         heapSort(array);
  65.         for (int item: array) {
  66.             System.out.print(item + " ");
  67.         }
  68.         System.out.println();
  69.     }
  70. }

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/163952?site
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号