【算法】排序算法(插入排序、希尔排序、选择排序、冒泡排序、快速排序、归并排序、基数排序、堆排序)

目录

• 一.常见排序类型
• 二.排序详解
• • 1.冒泡排序
  • 2.选择排序
  • 3.插入排序
  • 4.希尔排序
  • 5.快速排序
  • 6.归并排序
  • 7.基数排序(桶排序)
  • 8.堆排序
  • 三.���序算法比较

    一.常见排序类型

    • 插入排序：插入排序、希尔排序
    • 选择排序：选择排序、堆排序
    • 交换排序：冒泡排序、快速排序
    • 归并排序
    • 基数排序(又叫桶排序)

      二.排序详解

      1.冒泡排序

      (1)思路图解

      从头开始比较相邻元素的值(就是从下标较小的元素开始)，使值较大的元素逐渐从前移向后部，就像水里的气泡一样，越来越大，向上冒。最终得到从小到大的一个序列。

      (2)算法实现(java)

      /** * 冒泡排序 * author：xinxin * 时间复杂度是(n*n) */public class GuLouSort {    public static void main(String[] args) {        int[] arr = {16,28,5,66,88}; //初始化数组        int temp = 0; //临时变量        for (int i = 0; i  arr[j+1]){ //如果前面的值大于前面的值，那就交换位置                    temp = arr[j];                    arr[j] = arr[j+1];                    arr[j+1] = temp;                }            }            System.out.println("第"+(i+1)+"趟，排序后的结果");            System.out.println(Arrays.toString(arr));        }    }}

      运行结果

      2.选择排序

      (1)思路图解

      先从arr[0] ~ arr[n-1]找到一个最小值，和arr[0]交换，在从arr[1] ~ arr[n-1]中找到最小值，和arr[1]交换，以此类推，最终得到一个从小到大排列的序列。

      (2)算法实现(java)

      /** * 选择排序 * author：xinxin * 时间复杂度是(n*n) */public class SelectSort {    public static void main(String[] args) {        int[] arr = {16,6,88,2}; //初始化数组        for (int i = 0; i  arr[j]){ //如果假定的最小值比他后面的值要大,记录下标和值(这个地方控制是从大到小排序还是从小到大排序)                    minIndex = j;    //记录下标                    minArr = arr[j]; //记录值                }            }            //交换值            if (minIndex != i){                arr[minIndex] = arr[i];                arr[i] = minArr;            }            System.out.println("第"+(i+1)+"轮结果为");            System.out.println(Arrays.toString(arr));        }    }}

      运行结果

      3.插入排序

      (1)思路图解

      n个元素，分成一个有序序列和无序序列，开始有序序列只有一个元素，无序序列包含n-1个元素，排序时每次从无序序列取出第一个元素，和有序序列的元素的排序码进行比较，然后放到合适的位置，最后形成新的有序序列。

      (2)算法实现(java)

      /** * 插入排序 * author：xinxin */public class InsertSort {    public static void main(String[] args) {        int[] arr = {18, 6, 26, 15,  21,10};//初始化数组        for (int i = 1; i = 0 && currValue  
      运行结果
       
      4.希尔排序
       
      (1)思路图解
         
      希尔排序也是一种插入排序，但是更加高效，也称为速效增量排序。
      按照一定的增量(步长)进行分组，然后对每组进行插入排序，随着增量减少，每组的元素就越多，当增量减至1时，元素被分为一组，算法结束。
         
      (2)算法实现(交换法)
       
      /** * 希尔排序(交换法) * author：xinxin */public class ShellSort {    public static void main(String[] args) {        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};//初始数组        int temp = 0;        int count = 0;        //增量        for (int gap = arr.length/2; gap > 0; gap=gap/2){            //遍历组中所有元素，gap为步长            for (int i = gap; i = 0; j = j-gap){                    //如果当前元素大于加上步长的元素，那就交换位置                    if (arr[j] > arr[j+gap]){                        temp = arr[j];                        arr[j] = arr[j+gap];                        arr[j+gap] = temp;                    }                }            }            System.out.println("希尔排序(交换法)第"+(++count)+"轮的结果");            System.out.println(Arrays.toString(arr));        }    }}
       
      运行结果(交换法)
       
      (3)算法实现(移动法)
       
      /** * 希尔排序(移动法) * author：xinxin */public class ShellSort2 {    public static void main(String[] args) {        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};//初始数组        int count = 0;        for (int gap = arr.length/2; gap > 0; gap = gap/2){            //从第gap元素开始进行插入排序            for (int i = gap; i                int j = i;                int temp = arr[j];                if (arr[i]  
      运行结果(移动法)
       
      5.快速排序
       
      (1)思路图解
         
      快速排序是对冒泡排序的一种改进。
      基本思想是：把需要排序的元素分成两部分，一部分比另一部分都要小，然后进行快速排序，然后递归，最终得到有序序列。
        
      这个图是以第一个元素为中间值分割。（黄色的就相当于中间值，然后把比大小分成两组）
       
      (2)算法实现(java)
       
      /** * 快速排序 * author：xinxin */public class QuikeSort {    public static void main(String[] args) {        int[] arr = {1, 66, 2, 28, 0, 18};        quickeSotr(arr,0,arr.length-1);        System.out.println("快速排序结果为"+ Arrays.toString(arr));    }    public static void quickeSotr(int arr[],int left,int right){        int l = left;//左下标        int r = right;//右下标        int center = arr[(l + r)/2];//中间值        int temp = 0;//临时变量        //找到比center值小的放左边，比center值大的放右边        while(l  center){                r = r - 1;            }            //证明左边都是小于center的数，右边都是大于center的数            if (l >= r){                break;            }            //交换变量            temp = arr[l];            arr[l] = arr[r];            arr[r] = temp;            //前移            if (arr[l] == center){                r = r - 1;            }            //后移            if (arr[r] == center){                l = l + 1;            }        }        //如果相等必须进行下面操作，不然会栈溢出        if (l == r){            l = l + 1;            r = r - 1;        }        //向左递归        if (left  l){            quickeSotr(arr,l,right);        }    }}
       
      运行结果
       
      6.归并排序
       
      (1)思路图解
       
      利用归并的思想实现排序，采用分治策略：将问题分成小的问题然后递归求解，而治的阶段将分的阶段得到的结果放一起组合，即分而治之。
       
      下面治的阶段相当于 [4,5,7,8]和[1,2,3,6]各有指针去移动比较两个数组元素大小(和快速排序移动指针一样)，然后放入新的数组。
        
      (2)算法实现(java)
       
      public class MergeSort {    public static void main(String[] args) {        int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};        int[] temp = new int[arr.length];        mergeSort(arr,0,arr.length-1,temp);        System.out.println("归并排序结果为"+ Arrays.toString(arr));    }    /**     * 分 + 合     * @param arr     * @param left     * @param right     * @param temp     */    public static void mergeSort(int[] arr, int left, int right, int[] temp) {        if (left