首页 > 编程语言 >十大经典排序算法总结

十大经典排序算法总结

时间：2023-05-23 16:23:56浏览次数：44  
标签：arr int 复杂度 maxValue 算法 经典 序列 排序

排序算法可以分为：

  • 内部排序：数据记录在内存中进行排序。
  • 外部排序：因排序的数据很大，内存不能容纳全部的排序记录，在排序过程中需要访问外存。

常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序、计数排序、桶排序。

其中比较类排序有：冒泡排序、快速排序、插入排序、希尔排序、选择排序、堆排序、归并排序

非比较类排序：计数排序、基数排序、桶排序

 1、冒泡排序

算法步骤：从头或尾开始比较相邻的元素，如果逆序则交换，这样每遍历一次就会确定一个数的位置，重复以上步骤知道排序完成

 1 public int[] bubbleSort(int[] arr){
 2     for(int i=1;i<arr.length;i++){
 3         boolean flag=true;
 4         for(int j=0;j<arr.length-i;j++){
 5             if(arr[j]>arr[j+1]){
 6                 int temp=arr[j];
 7                 arr[j]=arr[j+1];
 8                 arr[j+1]=temp;
 9                 flag=false;
10             }
11         }
12         if(flag)break;
13     }
14     return arr;
15 }
bubbleSort

此处对代码做了一个小优化，加入了 is_sorted Flag，目的是将算法的最佳时间复杂度优化为 O(n)，即当原输入序列就是排序好的情况下，该算法的时间复杂度就是 O(n)。

算法分析：

  • 稳定性：稳定
  • 时间复杂度：最佳：O(n) ，最差：O(n2)， 平均：O(n2)
  • 空间复杂度：O(1)
  • 排序方式：交换排序

2、选择排序

算法步骤：从未排序的序列找到最小或者最大的放在指定位置，直到所有元素均有序

 1 public static int[] selectionSort(int[] arr) {
 2     for (int i = 0; i < arr.length - 1; i++) {
 3         int minIndex = i;
 4         for (int j = i + 1; j < arr.length; j++) {
 5             if (arr[j] < arr[minIndex]) {
 6                 minIndex = j;
 7             }
 8         }
 9         if (minIndex != i) {
10             int tmp = arr[i];
11             arr[i] = arr[minIndex];
12             arr[minIndex] = tmp;
13         }
14     }
15     return arr;
16 }
selectionSort

算法分析：

  • 稳定性：不稳定
  • 时间复杂度：最佳：O(n2) ，最差：O(n2)， 平均：O(n2)
  • 空间复杂度：O(1)
  • 排序方式：选择排序

3、插入排序

步骤：对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

public static int[] insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int preIndex = i - 1;
        int current = arr[i];
        while (preIndex >= 0 && current < arr[preIndex]) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex -= 1;
        }
        arr[preIndex + 1] = current;
    }
    return arr;
}

　　

  • 稳定性：稳定
  • 时间复杂度：最佳：O(n) ，最差：O(n2)， 平均：O(n2)
  • 空间复杂度：O(1)
  • 排序方式：插入排序

4、希尔排序

算法步骤：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录 “基本有序” 时，再对全体记录进行依次直接插入排序。

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

  • 选择一个增量序列 {t1, t2, …, tk}，其中 (ti>tj, i<j, tk=1)；
  • 按增量序列个数 k，对序列进行 k 趟排序；
  • 每趟排序，根据对应的增量 t，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
 1 public static int[] shellSort(int[] arr) {
 2     int n = arr.length;
 3     int gap = n / 2;
 4     while (gap > 0) {
 5         for (int i = gap; i < n; i++) {
 6             int current = arr[i];
 7             int preIndex = i - gap;
 8             // Insertion sort
 9             while (preIndex >= 0 && arr[preIndex] > current) {
10                 arr[preIndex + gap] = arr[preIndex];
11                 preIndex -= gap;
12             }
13             arr[preIndex + gap] = current;
14 
15         }
16         gap /= 2;
17     }
18     return arr;
19 }

算法分析：

  • 稳定性：不稳定
  • 时间复杂度：最佳：O(nlogn)， 最差：O(n2) 平均：O(nlogn)
  • 空间复杂度：O(1)

5、归并排序

归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

归并排序算法是一个递归过程，边界条件为当输入序列仅有一个元素时，直接返回，具体过程如下：

  1. 如果输入内只有一个元素，则直接返回，否则将长度为 n 的输入序列分成两个长度为 n/2 的子序列；
  2. 分别对这两个子序列进行归并排序，使子序列变为有序状态；
  3. 设定两个指针，分别指向两个已经排序子序列的起始位置；
  4. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间（用于存放排序结果），并移动指针到下一位置；
  5. 重复步骤 3 ~4 直到某一指针达到序列尾；
  6. 将另一序列剩下的所有元素直接复制到合并序列尾
 1 public static int[] mergeSort(int[] arr) {
 2     if (arr.length <= 1) {
 3         return arr;
 4     }
 5     int middle = arr.length / 2;
 6     int[] arr_1 = Arrays.copyOfRange(arr, 0, middle);
 7     int[] arr_2 = Arrays.copyOfRange(arr, middle, arr.length);
 8     return merge(mergeSort(arr_1), mergeSort(arr_2));
 9 }
10 
11 /**
12  * Merge two sorted arrays
13  *
14  * @param arr_1
15  * @param arr_2
16  * @return sorted_arr
17  */
18 public static int[] merge(int[] arr_1, int[] arr_2) {
19     int[] sorted_arr = new int[arr_1.length + arr_2.length];
20     int idx = 0, idx_1 = 0, idx_2 = 0;
21     while (idx_1 < arr_1.length && idx_2 < arr_2.length) {
22         if (arr_1[idx_1] < arr_2[idx_2]) {
23             sorted_arr[idx] = arr_1[idx_1];
24             idx_1 += 1;
25         } else {
26             sorted_arr[idx] = arr_2[idx_2];
27             idx_2 += 1;
28         }
29         idx += 1;
30     }
31     if (idx_1 < arr_1.length) {
32         while (idx_1 < arr_1.length) {
33             sorted_arr[idx] = arr_1[idx_1];
34             idx_1 += 1;
35             idx += 1;
36         }
37     } else {
38         while (idx_2 < arr_2.length) {
39             sorted_arr[idx] = arr_2[idx_2];
40             idx_2 += 1;
41             idx += 1;
42         }
43     }
44     return sorted_arr;
45 }
mergeSort

算法分析：

  • 稳定性：稳定
  • 时间复杂度：最佳：O(nlogn)， 最差：O(nlogn)， 平均：O(nlogn)
  • 空间复杂度：O(n)

6、快速排序

具体算法描述如下：

  1. 从序列中随机挑出一个元素，做为 “基准”(pivot)；
  2. 重新排列序列，将所有比基准值小的元素摆放在基准前面，所有比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个操作结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
  3. 递归地把小于基准值元素的子序列和大于基准值元素的子序列进行快速排序。
 1         public static void quicksort(int[] arr, int left, int right) {
 2             if (right >= left) {
 3                 //保存基数
 4                 int pivot = arr[left];
 5                 //定义左右指针
 6                 int i = left;
 7                 int j = right;
 8                 while (i < j) {        //左指针小于右指针
 9                     while (i < j && arr[j] > pivot) {//操作右指针找到小于基数的下标
10                         j--;
11                     }
12                     if (i < j) {
13                         arr[i] = arr[j];    //将右指针对应小于基数的值放到左指针所指的位置
14                         i++;                //左指针自加
15                     }
16                     while (i < j && arr[i] < pivot) {//相反，找到大于基数的下标
17                         i++;
18                     }
19                     if (i < j) {
20                         arr[j] = arr[i];    //大于基数的值赋给右指针所指的位置
21                         j--;                //右指针自减
22                     }
23                 }
24                 arr[i] = pivot;                //将基数放入到指针重合处
25                 quicksort(arr, left, i - 1);    //重复调用，对左半部分数组进行排序
26                 quicksort(arr, i + 1, right);    //对右半部分数组进行排序
27             }
28         }
quickSort

算法分析：

  • 稳定性：不稳定
  • 时间复杂度：最佳：O(nlogn)， 最差：O(nlogn)，平均：O(nlogn)
  • 空间复杂度：O(nlogn)

7、堆排序

堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子结点的值总是小于（或者大于）它的父节点。

算法步骤：

  • 将初始待排序列 (R1, R2, ……, Rn) 构建成大顶堆，此堆为初始的无序区；
  • 将堆顶元素 R[1] 与最后一个元素 R[n] 交换，此时得到新的无序区 (R1, R2, ……, Rn-1) 和新的有序区 (Rn), 且满足 R[1, 2, ……, n-1]<=R[n]；
  • 由于交换后新的堆顶 R[1] 可能违反堆的性质，因此需要对当前无序区 (R1, R2, ……, Rn-1) 调整为新堆，然后再次将 R [1] 与无序区最后一个元素交换，得到新的无序区 (R1, R2, ……, Rn-2) 和新的有序区 (Rn-1, Rn)。不断重复此过程直到有序区的元素个数为 n-1，则整个排序过程完成
 1 private static void swap(int[] arr, int i, int j) {
 2     int tmp = arr[i];
 3     arr[i] = arr[j];
 4     arr[j] = tmp;
 5 }
 6 private static void buildMaxHeap(int[] arr) {
 7     for (int i = arr.length / 2 - 1; i >= 0; i--) {
 8         heapify(arr, i);
 9     }
10 }
11 
12 private static void heapify(int[] arr, int i) {
13     int left = 2 * i + 1;
14     int right = 2 * i + 2;
15     int largest = i;
16     if (right < heapLen && arr[right] > arr[largest]) {
17         largest = right;
18     }
19     if (left < heapLen && arr[left] > arr[largest]) {
20         largest = left;
21     }
22     if (largest != i) {
23         swap(arr, largest, i);
24         heapify(arr, largest);
25     }
26 }
27 
28 public static int[] heapSort(int[] arr) {
29     // index at the end of the heap
30     heapLen = arr.length;
31     // build MaxHeap
32     buildMaxHeap(arr);
33     for (int i = arr.length - 1; i > 0; i--) {
34         // Move the top of the heap to the tail of the heap in turn
35         swap(arr, 0, i);
36         heapLen -= 1;
37         heapify(arr, 0);
38     }
39     return arr;
40 }
heapSort

算法分析：

  • 稳定性：不稳定
  • 时间复杂度：最佳：O(nlogn)， 最差：O(nlogn)， 平均：O(nlogn)
  • 空间复杂度：O(1)

8、计数排序

计数排序使用一个额外的数组 C，其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数。然后根据数组 C 来将 A 中的元素排到正确的位置。它只能对整数进行排序。

  • 找出数组中的最大值 max、最小值 min；
  • 创建一个新数组 C，其长度是 max-min+1，其元素默认值都为 0；
  • 遍历原数组 A 中的元素 A[i]，以 A[i]-min 作为 C 数组的索引，以 A[i] 的值在 A 中元素出现次数作为 C[A[i]-min] 的值；
  • 对 C 数组变形，新元素的值是该元素与前一个元素值的和，即当 i>1 时 C[i] = C[i] + C[i-1]；
  • 创建结果数组 R，长度和原始数组一样。
  • 从后向前遍历原始数组 A 中的元素 A[i]，使用 A[i] 减去最小值 min 作为索引，在计数数组 C 中找到对应的值 C[A[i]-min]，C[A[i]-min]-1 就是 A[i] 在结果数组 R 中的位置，做完上述这些操作，将 count[A[i]-min] 减小 1。
 1 /**
 2  * Gets the maximum and minimum values in the array
 3  *
 4  * @param arr
 5  * @return
 6  */
 7 private static int[] getMinAndMax(int[] arr) {
 8     int maxValue = arr[0];
 9     int minValue = arr[0];
10     for (int i = 0; i < arr.length; i++) {
11         if (arr[i] > maxValue) {
12             maxValue = arr[i];
13         } else if (arr[i] < minValue) {
14             minValue = arr[i];
15         }
16     }
17     return new int[] { minValue, maxValue };
18 }
19 
20 /**
21  * Counting Sort
22  *
23  * @param arr
24  * @return
25  */
26 public static int[] countingSort(int[] arr) {
27     if (arr.length < 2) {
28         return arr;
29     }
30     int[] extremum = getMinAndMax(arr);
31     int minValue = extremum[0];
32     int maxValue = extremum[1];
33     int[] countArr = new int[maxValue - minValue + 1];
34     int[] result = new int[arr.length];
35 
36     for (int i = 0; i < arr.length; i++) {
37         countArr[arr[i] - minValue] += 1;
38     }
39     for (int i = 1; i < countArr.length; i++) {
40         countArr[i] += countArr[i - 1];
41     }
42     for (int i = arr.length - 1; i >= 0; i--) {
43         int idx = countArr[arr[i] - minValue] - 1;
44         result[idx] = arr[i];
45         countArr[arr[i] - minValue] -= 1;
46     }
47     return result;
48 }
countingSort

算法分析：

当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 O(n+k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组 C 的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上 1），这使得计数排序对于数据范围很大的数组，需要大量额外内存空间。

  • 稳定性：稳定
  • 时间复杂度：最佳：O(n+k) 最差：O(n+k) 平均：O(n+k)
  • 空间复杂度：O(k)
9、桶排序 算法步骤：
  • 设置一个 BucketSize，作为每个桶所能放置多少个不同数值；
  • 遍历输入数据，并且把数据依次映射到对应的桶里去；
  • 对每个非空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序；
  • 从非空桶里把排好序的数据拼接起来
 1 private static int[] getMinAndMax(List<Integer> arr) {
 2     int maxValue = arr.get(0);
 3     int minValue = arr.get(0);
 4     for (int i : arr) {
 5         if (i > maxValue) {
 6             maxValue = i;
 7         } else if (i < minValue) {
 8             minValue = i;
 9         }
10     }
11     return new int[] { minValue, maxValue };
12 }
13 
14 
15 public static List<Integer> bucketSort(List<Integer> arr, int bucket_size) {
16     if (arr.size() < 2 || bucket_size == 0) {
17         return arr;
18     }
19     int[] extremum = getMinAndMax(arr);
20     int minValue = extremum[0];
21     int maxValue = extremum[1];
22     int bucket_cnt = (maxValue - minValue) / bucket_size + 1;
23     List<List<Integer>> buckets = new ArrayList<>();
24     for (int i = 0; i < bucket_cnt; i++) {
25         buckets.add(new ArrayList<Integer>());
26     }
27     for (int element : arr) {
28         int idx = (element - minValue) / bucket_size;
29         buckets.get(idx).add(element);
30     }
31     for (int i = 0; i < buckets.size(); i++) {
32         if (buckets.get(i).size() > 1) {
33             buckets.set(i, sort(buckets.get(i), bucket_size / 2));
34         }
35     }
36     ArrayList<Integer> result = new ArrayList<>();
37     for (List<Integer> bucket : buckets) {
38         for (int element : bucket) {
39             result.add(element);
40         }
41     }
42     return result;
43 }
bucketSort

算法分析：

  • 稳定性：稳定
  • 时间复杂度：最佳：O(n+k) 最差：O(n²) 平均：O(n+k)
  • 空间复杂度：O(k)

10、基数排序

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。

 1 public static int[] radixSort(int[] arr) {
 2     if (arr.length < 2) {
 3         return arr;
 4     }
 5     int N = 1;
 6     int maxValue = arr[0];
 7     for (int element : arr) {
 8         if (element > maxValue) {
 9             maxValue = element;
10         }
11     }
12     while (maxValue / 10 != 0) {
13         maxValue = maxValue / 10;
14         N += 1;
15     }
16     for (int i = 0; i < N; i++) {
17         List<List<Integer>> radix = new ArrayList<>();
18         for (int k = 0; k < 10; k++) {
19             radix.add(new ArrayList<Integer>());
20         }
21         for (int element : arr) {
22             int idx = (element / (int) Math.pow(10, i)) % 10;
23             radix.get(idx).add(element);
24         }
25         int idx = 0;
26         for (List<Integer> l : radix) {
27             for (int n : l) {
28                 arr[idx++] = n;
29             }
30         }
31     }
32     return arr;
33 }
radixSort

算法分析：

  • 稳定性：稳定
  • 时间复杂度：最佳：O(n×k) 最差：O(n×k) 平均：O(n×k)
  • 空间复杂度：O(n+k)

 

标签：arr,int,复杂度,maxValue,算法,经典,序列,排序
From： https://www.cnblogs.com/coooookie/p/17425567.html

相关文章

  • Day_01--C#递归算法
     ///递归算法本质：///1、方法的自我调用///2、有明确的终止条件///3、每次调用时，问题规模在不断减少。通过递减，最终到达终止条件 问题：程序在输入1000后（即1到1000的和），程序会出现异常。解答：百度后得出结论，栈溢出异常。1、递归方法在每......
  • 代码随想录算法训练营第十四天|144. 二叉树的前序遍历、145. 二叉树的后序遍历、94.
    【参考链接】1.满二叉树，完全二叉树，二叉搜索树（有数值，有序树）。2.平衡二叉搜索树：又被称为AVL（Adelson-VelskyandLandis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。3.优先级队列其实是一个堆，堆就是一棵完全二叉......
  • 8百多经典古诗学习鉴赏ACCESS\EXCEL数据库
    虽然古诗类的数据搞到过很多，但是有鉴赏、译文等鉴赏类字段的还是很少，而今天搞到一个古诗学习类数据库，虽然记录数不多，但大都有翻译、鉴赏、译文等字段内容，是小学生、中学生、高中生学习的好东西。朝代统计：金朝（2）、两汉（22）、明代（25）、南北朝（24）、清代（27）、宋代（348）、唐代（373）、魏晋（19）、五......
  • 算法刷题记录：NC22227 约瑟夫环
    题目链接https://ac.nowcoder.com/acm/problem/22227解题思路模拟环。这道题顺序数就行，顺序是逆时针，逆时针的箭头是往左拐的，变成直线后趋于正半轴所以是+。不过，这道模拟环并没有说从idx号开始，往左/右数几个人，所以不需要考虑+或-。因为不会越界，所以也不用额外%n。AC代码......
  • 基于PSO优化的SVM数据预测算法matlab仿真
    1.算法仿真效果matlab2022a仿真结果如下：     2.算法涉及理论知识概要         支持向量机（supportvectormachines,SVM）是二分类算法，所谓二分类即把具有多个特性（属性）的数据分为两类，目前主流机器学习算法中，神经网络等其他机器学习模型已经能很好完成二分......
  • m基于matlab的LDPC译码算法性能仿真,对比BP译码,最小和译码以及归一化偏移最小和译码
    1.算法仿真效果matlab2022a仿真结果如下：  2.算法涉及理论知识概要       LDPC码是麻省理工学院RobertGallager于1963年在博士论文中提出的一种具有稀疏校验矩阵的分组纠错码。几乎适用于所有的信道，因此成为编码界近年来的研究热点。它的性能逼近香农极限，且描述和......
  • 启发式算法在三维装箱问题上的应用
    启发式算法的出现时间比较难以确定，因为很多算法的提出都是在不同的领域和不同的时间段内，而且随着时间的推移，这些算法也在不断地完善和发展。以下是一些比较有代表性的启发式算法及其出现时间：1953年，模拟退火算法（SimulatedAnnealing，SA）模拟退火算法是一种基于固体物理学中固体退火......
  • 图解LeetCode——769. 最多能完成排序的块（难度：中等）
    一、题目给定一个长度为n的整数数组arr，它表示在[0,n-1]范围内的整数的排列。我们将arr分割成若干块(即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。返回数组能分成的最多块数量。二、示例2.1>示例1:【输入】arr=[4,3,2,......
  • 代码随想录算法训练营第9天 | ●28. 实现 strStr() ●459.重复的子字符串 ●字符串总
     第四章 字符串part02今日任务  ● 28. 实现 strStr()● 459.重复的子字符串● 字符串总结 ● 双指针回顾   详细布置  28. 实现 strStr()  （本题可以跳过） 因为KMP算法很难，大家别奢求 一次就把kmp全理解了，大家刚学KMP一定会有各种各样的疑问......
  • 代码随想录算法训练营第10天 | ● 理论基础 ● 232.用栈实现队列 ● 225. 用队列实现
     第五章 栈与队列part01●  day 1 任务以及具体安排：训练营一期day 1 ●  day 2 任务以及具体安排：day 2 第一章数组●  day 3 任务以及具体安排：day 3 第二章 链表●  day 4 任务以及具体安排：day 4 第二章 链表●  day 5 周日休息●  ......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99