各种常用排序算法的总结

深碍√TFBOYSˉ_ 2022-02-27 11:12 232阅读 0赞

# 各大常用排序算法总结 #

排序算法为最基础,而有最常用的算法,下面列举了冒泡排序,选择排序,插入排序,快速排序.算法总结均为个人的理解,用于以后如果遗忘能够快速回忆.

## 1.冒泡排序 ##

**思想:** 将需要排序的数组的n个元素看做一个个气泡,每次浮出一个最大的,**需要浮出n - 1次**(最后一个元素自然在正确的位置,不用进行排序).要想使得气泡可以浮出来,需要不断进行比较交换,将最大的气泡冒出来,**需要比较n - 1次**,每次进行一轮浮出就排好了一个元素,所以应把排好的数量减去.利用这样的双重for循环,就成功完成了排序.

改进:如果有一次排序中全程没有发生交换,说明顺序已经排好,不必在进行后续遍历了,设置标志位进行判断即可.

/** * @author BestQiang */
    public class BubbleSort { 
        // 算法不允许产生任何实例
        private BubbleSort() { 
        }
    
        public static void sort1(int[] arr) { 
            for (int i = 0; i < arr.length - 1; i++) { // 第一次for循环表示需要排序n - 1趟
                for (int j = 0; j < arr.length - i - 1; j++) { // 第二次for循环表示需要进行n - 1次比较交换
                    if (arr[j] > arr[j + 1]) { 
                        int tmp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = tmp;
                    }
                }
            }
        }
    
        // 改进后的冒泡排序,设置标志k,当一次遍历中没有发生交换,说明已经完成所有排序,不必在进行后续遍历
        public static void sort2(int arr[]) { 
            boolean k;
            for (int i = 0; i < arr.length - 1; i++) { 
                k = false;
                for (int j = 0; j < arr.length - i - 1; j++) { 
                    if (arr[j] > arr[j + 1]) { 
                        int tmp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = tmp;
                        k = true;
                    }
                }
                if (!k) { 
                    break;
                }
            }
        }
    
    
        public static void main(String[] args) { 
            int[] arr = new int[]{ 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
            BubbleSort.sort7(arr);
            for (int i : arr) { 
                System.out.print(i);
                System.out.print(" ");
            }
        }
    }

**百度百科的介绍:** 冒泡排序（Bubble Sort），是一种[计算机科学][Link 1]领域的较简单的[排序算法][Link 2]。

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。冒泡排序的**时间复杂度为O(n^2),空间复杂度为O(1)**,它是一种稳定的排序算法。

## 2.选择排序 ##

**思想:** 选择排序,就如它的名字一样,就是每次选择最小的,从第一个位置依次往后放置,就完成了排序.算法也简单,**使用两个for循环,一个用来遍历位置,一个用来寻找最小的值.注意放置的时候不能直接赋值,这样会导致当前的值直接被覆盖,所以将当前位置的值与所找到的最小值进行交换即可,等待下一次挑选.**

package sort;
    
    /** * @author BestQiang */
    public class SelectionSort { 
        // 算法不允许产生任何实例
        private SelectionSort() { 
        }
    
        private static void sort(int arr[]) { 
            for (int i = 0; i < arr.length; i ++) { 
                // 寻找当前排序位置以及之后最小值的坐标
                int minIndex = i;
                for(int j = i + 1; j < arr.length; j++) { 
                    if(arr[j] < arr[minIndex]) { 
                        minIndex = j;
                    }
                }
                // 找到后将这个坐标与当前的排序位置的坐标进行互换
                swap(arr, i, minIndex);
            }
        }
    
        private static void swap(int[] arr, int i, int minIndex) { 
            int t = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = t;
        }
    
        public static void main(String[] args) { 
            int[] arr = new int[]{ 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
            SelectionSort.sort(arr);
            for (int i : arr) { 
                System.out.print(i);
                System.out.print(" ");
            }
        }
    }

**百度百科的介绍:选择排序（Selection sort）是一种简单直观的[排序算法][Link 2]。它的工作原理是每一次从待排序的[数据元素][Link 3]中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法**。

## 3.插入排序 ##

**思想:** 就像玩扑克牌一样,拿到第一张牌,然后第二张牌拿到后和第一张牌比较,放到合适的位置,依次类推,拿到一张新牌,把它插到手里已经排好的牌当中即可.**将要排序的数组的元素比作牌,实现这个算法,首先要用一个for循环记录当前拿到的牌,然后再用一个for循环,用来将它和手中已经排好的牌进行比较,放到合适的位置即可.**

package sort;
    
    /** * @author BestQiang */
    public class InsertSort { 
        // 我们的算法不允许产生任何实例
        private InsertSort() { 
        }
    
        public static void sort(Comparable[] arr) { 
            int n = arr.length;
            for (int i = 0; i < n; i++) { 
                // 寻找元素arr[i]合适的插入位置
                // 写法1
                /*for (int j = i; j > 0; j--) { // 进行比较交换,一直到合适的位置 if(arr[j].compareTo(arr[j-1]) < 0) { Comparable tmp = arr[j]; arr[j] = arr[j -1]; arr[j-1] = tmp; }else { break; } }*/
                // 写法2,将比较提到条件中
                /*for (int j = i; j > 0 && arr[j].compareTo(arr[j-1]) < 0; j--) { Comparable tmp = arr[j]; arr[j] = arr[j -1]; arr[j-1] = tmp; }*/
            }
            // 优化写法,省去不必要的交换
            for (int i = 1; i < n; i++) { 
                // 寻找元素arr[i]合适的插入位置
                Comparable e = arr[i];
                int j; // j保存元素e应该插入的位置
                for (j = i; j > 0 && arr[j - 1].compareTo(e) > 0; j--) { 
                    // 找到后不需交换,直接赋值即可
                    arr[j] = arr[j - 1];
                }
                arr[j] = e;
            }
        }
        
        public static void main(String[] args) { 
            Integer[] arr = new Integer[]{ 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
            InsertSort.sort(arr);
            for (int i : arr) { 
                System.out.print(i);
                System.out.print(" ");
            }
        }
    }

**百度百科的介绍:** 一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——[插入排序法][Link 4],插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，[时间复杂度][Link 5]为**O(n^2)**。是稳定的排序方法。插入算法把要排序的[数组][Link 6]分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

## 4.快速排序 ##

**思想:** 核心思想就是,找一个基准元素,通过一趟排序将数组中的元素分为两个部分,其中一部分比基准元素小,另外一部分比基准元素大,此时基准元素已经处于正确的位置了,然后再次递归调用,分别对左右两部分进行排序,以此达到整个序列有序.递归,使得算法变得简单.

package sort;
    
    /** * @author BestQiang */
    public class QuickSort { 
    
        // 我们的算法类不允许产生任何实例
        private QuickSort() { 
        }
    
    
        // 这是用于快速排序的调用
        private static void sort(int[] arr) { 
            int n = arr.length;
            sort(arr, 0, n - 1);
        }
    
        // 这是快速排序的主体实现
        private static void sort(int[] arr, int l, int r) { 
            // 递归使用快速排序,对arr[l...r]的范围进行排序
            // 设置终止条件
            if (l > r) { 
                return;
            }
            // 获取基准点,并排序,使得基准点在正确的位置
            int p = partition(arr, l, r);
            // 一次排好后,递归调用,再次对左右两边的元素分别进行排序
            sort(arr, l, p - 1);
            sort(arr, p + 1, r);
        }
    
        // 对arr[l...p-1] < arr[p]; arr[p+1...r] > arr[p]
        private static int partition(int[] arr, int l, int r) { 
            // 选取最左边的元素作为基准点,用于下面for循环中的比较
            int v = arr[l];
            // 设置j作为基准点位置返回值,此时默认值就是最左边的l
            int j = l; // arr[l+1...j] < v arr[j+1,...i] > v
            // 核心算法,从基准点初始值+1的位置比较,即l+1的位置,如果当前值比基准点要小,就
            // 将基准点的位置加上1,然后将当前值与基准点位置互换(就相当于使基准点位置一直位于左边部分的尾部)
            // 就这样把元素遍历一遍之后,将基准点的值换到对应的位置即可(基准点的值一直在l位置,没有变)
            for (int i = l + 1; i <= r; i++) { 
                if (arr[i] < v) { 
                    j++;
                    swap(arr, j, i);
                }
            }
            swap(arr, l, j);
            return j;
        }
    
        private static void swap(int[] arr, int j, int i) { 
            int tmp = arr[j];
            arr[j] = arr[i];
            arr[i] = tmp;
        }
    
        public static void main(String[] args) { 
            int[] arr = new int[]{ 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    
            QuickSort.sort(arr);
            for (int i : arr) { 
                System.out.print(i);
                System.out.print(" ");
            }
        }
    }

**百度百科的介绍:** 快速排序（Quicksort）是对[冒泡排序][Link 7]的一种改进。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以[递归][Link 8]进行，以此达到整个数据变成有序[序列][Link 9]。快速排序的时间复杂度为**O (nlogn)**.

[Link 1]: https://baike.baidu.com/item/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6
[Link 2]: https://baike.baidu.com/item/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/5399605
[Link 3]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E5%85%83%E7%B4%A0/715313
[Link 4]: https://baike.baidu.com/item/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E6%B3%95/612261
[Link 5]: https://baike.baidu.com/item/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6/1894057
[Link 6]: https://baike.baidu.com/item/%E6%95%B0%E7%BB%84/3794097
[Link 7]: https://baike.baidu.com/item/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F/4602306
[Link 8]: https://baike.baidu.com/item/%E9%80%92%E5%BD%92/1740695
[Link 9]: https://baike.baidu.com/item/%E5%BA%8F%E5%88%97/1302588