【算法刷题】八大排序算法总结(冒泡、选择、插入、二分插入、归并、快速、希尔、堆排序)

发布于:2024-04-10 ⋅ 阅读:(166) ⋅ 点赞:(0)

在这里插入图片描述

八大排序算法总结

排序 排序方法 平均情况 最好情况 最坏情况 空间 稳定性
1 冒泡排序 O(n2) O(n) O(n2) O(1) 稳定
2 选择排序 O(n2) O(n2) O(n2) O(1) 不稳定
3 插入排序 O(n2) O(n) O(n2) O(1) 稳定
4 二分插入排序 O(n2) O(n) O(n2) O(1) 稳定
5 归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
6 快速排序 O(nlogn) O(nlogn) O(n2) O(logn)~O(n) 不稳定
7 希尔排序 O(nlogn) ~ O(n2) O(n1.3) O(n2) O(1) 不稳定
8 堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定

1.冒泡排序

  1. 核心思想: 通过相邻元素的比较和交换来将最大(或最小)的元素逐渐“冒泡”到数组的一端

    动图

  2. 具体步骤:

    1. 从数组的第一个元素开始,依次比较相邻的两个元素。
    2. 如果前一个元素大于后一个元素,则交换它们的位置,使得较大的元素“冒泡”到后面
    3. 继续进行相邻元素的比较和交换,直到数组的末尾
    4. 重复执行上述步骤,每次都会将当前未排序部分的最大元素“冒泡”到数组的末尾
    5. 重复执行上述步骤,直到整个数组排序完成。
  3. 实现代码:

    public static void bubbleSort(int[] arr) {
        int temp = 0;
        for (int i = arr.length - 1; i > 0; i--) { 	// 每次需要排序的长度
            for (int j = 0; j < i; j++) { 			// 从第一个元素到第i个元素
                if (arr[j] > arr[j + 1]) {			// 确保较大的元素排到后面
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
    
  4. 时间和空间复杂度:

    • 平均情况:O(n2)
    • 最好情况:O(n)
    • 最坏情况:O(n2)
    • 空间复杂度:O(1)
    • 稳定性:稳定
  5. 优化: 增加标记符swap,用于确定当前一轮冒泡是否有元素进行交换,若没有则跳出循环,表示数组已经有序了

    public static void bubbleSort(int[] arr) {
        int temp = 0;
        boolean swap;
        for (int i = arr.length - 1; i > 0; i--) { // 每次需要排序的长度
            swap=false;
            for (int j = 0; j < i; j++) { // 从第一个元素到第i个元素
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swap=true;
                }
            }//loop j
            if (swap==false){			//前面的一轮循环没有进行交换,数组已经有序
                break;
            }
        }//loop i
    }// method bubbleSort
    

2.选择排序

  1. 核心思想: 在未排序部分的数据中选择最小(或最大)的元素,然后将其放置到已排序部分的末尾

  2. 具体步骤:

    1. 遍历数组,将第一个元素作为当前最小(或最大)元素。
    2. 在未排序部分的剩余元素中,找到最小(或最大)的元素,并记录其位置。
    3. 将找到的最小(或最大)元素与未排序部分的第一个元素交换位置,将其放置到已排序部分的末尾。
    4. 重复执行上述步骤,每次都会将当前未排序部分的最小(或最大)元素放置到已排序部分的末尾。
    5. 这样,经过n-1轮的遍历和交换,整个数组就会按照升序(或降序)排列。
  3. 实现代码:

    public static void selectionSort(int[] arr) {
        int temp, min = 0;
        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;
                }
            }
            if (min != i) {
                temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
        }
    }
    
  4. 时间和空间复杂度:

    • 平均情况:O(n2)
    • 最好情况:O(n2)
    • 最坏情况:O(n2)
    • 空间复杂度:O(1)
    • 稳定性:不稳定
  5. 关于稳定性的探讨:

    • 稳定性:在排序过程中,相等元素的相对顺序是否会被改变。如果排序算法能够保持相等元素的相对顺序不变,则称其为稳定的排序算法;反之,则称其为不稳定的排序算法

    • 冒泡排序(升序):当相邻元素进行比较并需要交换位置时,只有当后面的元素小于前面的元素才会进行交换。因此,对于相等的元素,即使它们相邻,它们的相对顺序也不会被改变,从而保持了排序的稳定性

    • 选择排序:每次选择最小的元素并放置到已排序部分的末尾。在寻找最小(或最大)元素的过程中,可能会导致相等元素的相对顺序发生改变。例如,在一组相等的元素中,由于选择排序每次只选择一个最小(或最大)元素,所以在选择的过程中可能会交换这些相等元素的位置,从而导致排序的不稳定性

    • 举例:假设我们有以下一组待排序的元素:

      [5①, 2, 7, 5②, 1]
      
      • 冒泡排序:比较相邻的元素,并根据需要交换它们的位置。当遇到相等元素时,只有在后面的元素小于前面的元素时才会进行交换。

        第一轮冒泡排序:[2, 5①, 5②, 1, 7]
        第二轮冒泡排序:[2, 5, 1, 5, 7]
        第三轮冒泡排序:[2, 1, 5, 5, 7]
        第四轮冒泡排序:[1, 2, 5, 5, 7]
        
      • 选择排序:

        第一轮选择排序:[1, 2, 7, 5②, 5①](选择1) (两个相等的5的位置发生变化,不稳定!!!)
        第二轮选择排序:[1, 2, 5, 5, 7](选择2)
        第三轮选择排序:[1, 2, 5, 5, 7](选择5)
        第四轮选择排序:[1, 2, 5, 5, 7](选择5)
        第五轮选择排序:[1, 2, 5, 5, 7](选择7)
        

3.插入排序

  1. 核心思想:待排序的元素逐个插入到已排序部分的正确位置

    动图

  2. 具体步骤:

    1. 将数组分为已排序部分和未排序部分。一开始,已排序部分只包含第一个元素,即数组的第一个元素被认为是已排序的。
    2. 从未排序部分取出一个元素,将其插入到已排序部分的正确位置。为了找到正确的位置,可以从已排序部分的末尾开始,依次向前比较已排序元素,直到找到小于等于该元素的位置。
    3. 将该元素插入到找到的位置,并将已排序部分中的元素向后移动,为新元素腾出位置。
    4. 重复步骤2和步骤3,直到未排序部分为空。
    5. 最终,已排序部分即为排序好的数组。
  3. 实现代码:

    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {		//从第二个元素开始,第一个元素默认有序
        	int key = arr[i];				//保存当前元素 key
            int j = i - 1;
    		
            //找到合适的位置
            while (j >= 0 && arr[j] > key) {//发现已排序元素比 key 大,则将该元素向后移动一位,直到找到 key 的正确位置
            	arr[j + 1] = arr[j];
    			j = j - 1;					//往后移
            }	
            arr[j + 1] = key;1				//找到 key 保存的位置
       	}
    }
    
    待排序数组:[5, 2, 4, 6, 1, 3]
    1:[2, 5, 4, 6, 1, 3]
    2:[2, 4, 5, 6, 1, 3]
    3:[1, 2, 4, 5, 6, 3]
    4:[1, 2, 3, 4, 5, 6]
    
  4. 时间和空间复杂度:

    • 平均情况:O(n2)
    • 最好情况:O(n)
    • 最坏情况:O(n2)
    • 空间复杂度:O(1)
    • 稳定性:稳定

4.二分插入排序

  1. 核心思想:利用二分查找来确定待插入元素在已排序部分中的位置,以减少比较次数

  2. 实现步骤:

    1. 初始状态:将数组的第一个元素视为已排序部分,其余元素视为待排序部分。
    2. 插入过程:从第二个元素开始遍历待排序部分,对于每个元素,使用二分查找确定其在已排序部分中的插入位置。
    3. 二分查找:在已排序部分中,使用二分查找找到第一个大于待插入元素的位置,这个位置及之后的元素都需要向后移动一个位置来腾出空间。
    4. 插入操作:将待插入元素插入到找到的位置,完成一轮插入操作。
    5. 重复步骤2~4,直到待排序部分中的所有元素都被插入到已排序部分中,整个数组就被排序完成了。
  3. 实现代码:

    public static void binaryInsertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int left = 0;
            int right = i - 1;
    
            // 二分查找确定插入位置
            int insertIndex = binarySearch(arr, left, right, key);
    
            // 将大于 key 的元素向后移动一位
            for (int j = i - 1; j >= insertIndex; j--) {
                arr[j + 1] = arr[j];
            }
    
            // 插入 key
            arr[insertIndex] = key;
        }
    }
    
    // 二分查找
    private static int binarySearch(int[] arr, int left, int right, int key) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == key) {
                return mid; // key 在已排序部分的位置
            } else if (arr[mid] < key) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left; // 返回待插入位置
    }
    
  4. 时间和空间复杂度:

    • 平均情况:O(n2)
    • 最好情况:O(n)
    • 最坏情况:O(n2)
    • 空间复杂度:O(1)
    • 稳定性:稳定

5.归并排序

  1. 核心思想: 采用分治法,将已有序的子序列合并,得到完全有序的序列;

  2. 步骤:

    1. 分解(Divide):将原始数组分解为较小的子数组,直到每个子数组只有一个元素为止。这可以通过递归的方式实现,将数组不断二分直到每个子数组的长度为1。
    2. 解决(Conquer):对每个子数组进行排序。对于只有一个元素的子数组来说,可以认为它们已经是有序的。
    3. 合并(Merge):合并相邻的子数组,形成一个更大的有序数组。合并过程中,需要按照大小顺序逐个比较两个子数组中的元素,并将较小(或较大)的元素依次放入一个临时数组中,直到合并完成。
    4. 递归合并(Recursively Merge):重复以上步骤,直到所有子数组都被合并成一个大的有序数组为止。

    动图

  3. 实现代码:

    public static void mergeSort(int[] arr){
        int[] temp =new int[arr.length];
        internalMergeSort(arr, temp, 0, arr.length-1);
    }
    private static void internalMergeSort(int[] arr, int[] temp, int left, int right){
        //当left==right的时,已经不需要再划分了
        if (left<right){
            int middle = (left+right)/2;
            internalMergeSort(arr, temp, left, middle);          //左子数组
            internalMergeSort(arr, temp, middle+1, right);       //右子数组
            mergeSortedArray(arr, temp, left, middle, right);    //合并两个子数组
        }
    }
    // 合并两个有序子序列
    private static void mergeSortedArray(int arr[], int temp[], int left, int middle, int right){
        int i=left;      
        int j=middle+1;
        int k=0;
        while (i<=middle && j<=right){
            temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }
        while (i <=middle){
            temp[k++] = arr[i++];
        }
        while ( j<=right){
            temp[k++] = arr[j++];
        }
        //把数据复制回原数组
        for (i=0; i<k; ++i){
            arr[left+i] = temp[i];
        }
    }
    
  4. 时间和空间复杂度:

    • 平均情况:O(nlogn)
    • 最好情况:O(nlogn)
    • 最坏情况:O(nlogn)
    • 空间复杂度:O(n)
    • 稳定性:稳定
  5. 适用场景: 归并排序在数据量比较大的时候也有较为出色的表现(效率上),但是,其空间复杂度O(n)使得在数据量特别大的时候(例如,1千万数据)几乎不可接受。而且,考虑到有的机器内存本身就比较小,因此,采用归并排序一定要注意。

6.快速排序

  1. 核心思想: 通过选取基准元素,将数组划分为两个子数组,并对子数组递归排序,实现整个数组的快速排序

  2. 实现步骤:

    1. 从数列中挑出一个元素,称为 “基准”(pivot),
    2. 重新排序数列,所有比基准值小的元素摆放在基准前面所有比基准值大的元素摆在基准后面(相同的数可以到任何一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
    3. 递归地(recursively)把小于基准值元素的子数列大于基准值元素的子数列排序。
  3. 实现代码:

    public static void quickSort(int[] arr){
        qsort(arr, 0, arr.length-1);
    }
    
    private static void qsort(int[] arr, int low, int high){
        if (low >= high)
            return;
        int pivot = partition(arr, low, high);        //将数组分为两部分
        qsort(arr, low, pivot-1);                   //递归排序左子数组
        qsort(arr, pivot+1, high);                  //递归排序右子数组
    }
    
    private static int partition(int[] arr, int low, int high){
        int pivot = arr[low];     //基准
        while (low < high){
            
            while (low < high && arr[high] >= pivot){
                --high;
            } 
            
            arr[low]=arr[high];             //比基准小的元素会被移动到基准的左边
            
            while (low < high && arr[low] <= pivot){
                ++low;
            }
            
            arr[high] = arr[low];           //比基准大的元素会被移动到基准的右边
        }
        //扫描完成,基准到位
        arr[low] = pivot;
        //返回的是基准的位置
        return low;
    }
    
  4. 举例:

    初始:[7, 2, 1, 6, 8, 5, 3, 4]	# 7为基准
    	 
    第一:[4, 2, 1, 6, 8, 5, 3, 4] # 4移到左边
    	 [4, 2, 1, 6, 8, 5, 3, 8] # 8移到右边
    	 [4, 2, 1, 6, 3, 5, 3, 8] # 3移到左边
    	 [4, 2, 1, 6, 3, 5, 7, 8] # 基准7插入到low位置
    	 
    划分为两个数组:[4, 2, 1, 6, 3, 5]和[8]
    第二: [4, 2, 1, 6, 3, 5] # 以4为基准
    	  [3, 2, 1, 6, 3, 5] # 3移到左边
    	  [3, 2, 1, 6, 6, 5] # 6移到右边
    	  [3, 2, 1, 4, 6, 5] # 基准4插入到low位置
    	 
    以此类推......
    
  5. 时间和空间复杂度:

    • 平均情况:O(nlogn)
    • 最好情况:O(nlogn)
    • 最坏情况:O(n2)
    • 空间复杂度:O(logn)~O(n)
    • 稳定性:不稳定

7.希尔排序

  • 明天总结

8.堆排序

  • 明天总结

在这里插入图片描述


网站公告

今日签到

点亮在社区的每一天
去签到