数据结构与算法总结——排序(一)简单排序

xiaoxiao2021-02-28  27

  学习了数据结构这么久,发现自己往往在学习过程中只是注意了每一个算法的具体实现,但是忽略了算法之间的联系。在再一次的复习中,发现了一些有意思的地方,又梳理了一遍算法间的联系。在这里记录下自己的体会。

  本篇的主题是简单排序,作为算法复习的第一块肯定是排序啦,而简单排序又是其基础。这次就好好聊聊这些简单排序——冒泡排序,选择排序,插入排序,希尔排序。

1.冒泡排序:从头到尾扫描数组,每次相邻的两数两两比较,可将最大的移动到当前扫描范围的最后一个位置(假设按数组的升序排序)。下次扫描则忽略已经确定的最后一位,而是确定倒数第二位,直到剩下最后一个数为止。

import java.util.*; public class BubbleSort { public static int[] bubbleSort(int[] a, int N) { for(int i=0 ;i<N; i++){ //int min = a[i]; for(int j=0; j<N-i-1; j++){ if(a[j] > a[j+1]){ swap(a, j, j+1); } } } return a; } private static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } }

算法的时间复杂度为O(n*n),空间复杂度为O(1),且为稳定排序(相同元素在排序后不会交换次序)

冒泡排序的思想很简单:两两进行比较,若前面的数比后面的数大,则进行交换。从这里其实可以看出优化的办法,是不是可是只记录要交换位置的下标而不用真实的进行交换,从而提高算法效率呢? 其实这种想法就可以认为是我们要聊的第二个算法——选择排序了。

2.选择排序: 从头到位扫描数组,第一趟确定数组的最小值放在数组头,第二趟确定数组的次小值放在数组的第二个位置,直到最后一个元素为止。(其实选择排序一种变形就是每次选择最大值放在数组的最后一个,这样就可以认为是一个优化过的冒泡排序了)

import java.util.*; public class SelectionSort { public static int[] selectionSort(int[] A, int n) { for(int i=0; i<n; i++){ int min = i; for(int j=i+1; j<n; j++){ if(A[j] < A[min]){ min = j; } } swap(A, i, min); } return A; } private static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } }

算法的时间复杂度位O(n * n),空间复杂度为O(1),选择排序是不稳定排序,考虑到一个数组为 2(1号),2(2号),1,当第一趟确定位置时,2(1号)和1进行交换,在排序后2(2号)排在了2(1号)前面。所以为不稳定排序。

选择排序的思想也很直接:站在数组整体的角度上看,每次循环就可以确定排序后的数组其中的一个位置,那么我们当然也可以站在每个元素的角度上来排序数组,这就是我们下面要聊的排序——插入排序。

3.插入排序:(引用算法导论里的话)想象你要对一个牌进行排序,你的左手放的都是排好顺序的牌,右手每次拿起一张牌插入到左手中牌的合适的位置中去。

import java.util.*; public class InsertionSort { public static int[] insertionSort(int[] A, int n) { for(int i=1; i<n; i++){ for(int j=i; j>0 && A[j-1] > A[j]; j--){ swap(A, j, j-1); } } return A; } private static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } }

插入排序的时间复杂度也是O(n*n),空间复杂度为O(1)。插入排序是稳定的排序算法。

插入排序对于总体有序的数组排序的效果很好(可以粗略认为是常数级的)。插入排序有2种优化的方法,一种思路和对前面冒泡排序的优化一样,将本要进行交换的操作变成记录下标,直到找到那个合适插入的下标,再进行1次交换,一步到位。

第二种办法是改变交换的步长,就是我们下面要说的算法——Shell排序。

4.Shell排序

思想:利用多次步长由大到小的插入排序,克服了插入排序每次只能相邻元素进行交换导致的效率问题。可以想象为先进行“粗调”,再在“粗调”的基础上进行“细调”的过程。

import java.util.*; public class ShellSort { public static int[] shellSort(int[] A, int n) { int h = 1; while(h < n/3) h = 3*h + 1; while(h >=1){ for(int i=h; i<n; i++){ for(int j=i; j>h && A[j] < A[j-h]; j-=h){ swap(A, j, j-h); } } } return A; } private static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } }希尔排序的时间复杂度取决于使用的步长函数(不是我们现在研究的重点),一般认为它的时间复杂度在O(n*n)到O(nlgn)之间。空间复杂度为O(1),是不稳定的排序。

下篇文章我们接着聊聊排序的另一对兄弟——归并排序和快速排序 再加上堆排序。

转载请注明原文地址: https://www.6miu.com/read-1450177.html

最新回复(0)