Solo  当前访客:0 开始使用

Carson

记录精彩的程序人生

常见排序算法 有更新!

2019-04-23 15:23:19 dulinanaaa
0  评论    163  浏览

    • 冒泡排序(Bubble Sort)
      • 示意图
      • 算法实现
    // 冒泡排序,a 表示数组,n 表示数组大小
    
    public void bubbleSort(int[] a, int n) {
    
      if (n <= 1) return;
     
     for (int i = 0; i < n; ++i) {
        // 提前退出冒泡循环的标志位
        boolean flag = false;
        for (int j = 0; j < n - i - 1; ++j) {
          if (a[j] > a[j+1]) { // 交换
            int tmp = a[j];
            a[j] = a[j+1];
            a[j+1] = tmp;
            flag = true;  // 表示有数据交换      
          }
        }
        if (!flag) break;  // 没有数据交换,提前退出
      }
    }
    
    • 插入排序(Insertion Sort)
      • 示意图

      • 算法实现
    // 插入排序,a 表示数组,n 表示数组大小
    
    public void insertionSort(int[] a, int n) {
      if (n <= 1) return;
    
      for (int i = 1; i < n; ++i) {
        int value = a[i];
        int j = i - 1;
        // 查找插入的位置
        for (; j >= 0; --j) {
          if (a[j] > value) {
            a[j+1] = a[j];  // 数据移动
          } else {
            break;
          }
        }
        a[j+1] = value; // 插入数据
      }
    }
    
    • 选择排序(Selection Sort)

      • 示意图
    • 归并排序(Merge Sort)

      • 示意图
      • 算法实现
    递推公式:
    
    merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))
    
    终止条件:
    p >= r 不用再继续分解
    

    merge_sort方法如下:

    // 归并排序算法, A 是数组,n 表示数组大小
    
    merge_sort(A, n) {
      merge_sort_c(A, 0, n-1)
    }
    
    // 递归调用函数
    merge_sort_c(A, p, r) {
      // 递归终止条件
      if p >= r  then return
    
      // 取 p 到 r 之间的中间位置 q
      q = (p+r) / 2
      // 分治递归
      merge_sort_c(A, p, q)
      merge_sort_c(A, q+1, r)
      // 将 A[p...q] 和 A[q+1...r] 合并为 A[p...r]
      merge(A[p...r], A[p...q], A[q+1...r])
    }
    

    merge是将有序的两个数组合并成一个数组,
    其实现方式

    代码如下

    merge(A[p...r], A[p...q], A[q+1...r]) {
    
      var i := p,j := q+1,k := 0 // 初始化变量 i, j, k
      var tmp := new array[0...r-p] // 申请一个大小跟 A[p...r] 一样的临时数组
      while i<=q AND j<=r do {
        if A[i] <= A[j] {
          tmp[k++] = A[i++] // i++ 等于 i:=i+1
        } else {
          tmp[k++] = A[j++]
        }
      }
      
      // 判断哪个子数组中有剩余的数据
      var start := i,end := q
      if j<=r then start := j, end:=r
      
      // 将剩余的数据拷贝到临时数组 tmp
      while start <= end do {
        tmp[k++] = A[start++]
      }
      
      // 将 tmp 中的数组拷贝回 A[p...r]
      for i:=0 to r-p do {
        A[p+i] = tmp[i]
      }
    }
    

    附:归并算法的实现

    • 快速排序算法(Quicksort)
      • 伪示意图(为了便于理解,实际中用巧秒的原地算法,节省空间复杂度,而下面是非原地的)

      以最后一个元素的值为分界点,小于该数放在左边,大于该数放在右边,分界点放中间(三部分)。然后再向归并排序那样递归,直到p>=r

      • 算法实现
        上面那种的是非原地算法,占用内存空间,不可取。巧秒改成原地算法,代码如下:
    partition(A, p, r) {
      //选取最后一个元素A[r]作为分界值
      pivot := A[r] 
      // 初始i在首元素的位置(后续i的位置会往后移。i指向位置之前的元素,即图中6、11、3、9、8中,i之前的元素都是排好的小于8的值)
      i := p
      // 让j从数组0一直到最后
      for j := p to r-1 do {
        // 元素小于分界点的值,就将遍历的A[j](第j次遍历)与A[i](未排的首元素,它前面的都排好了)
        if A[j] < pivot {
          swap A[i] with A[j]
          //只有小于分界点才交换,i的位置下标也间接说明是它已交换的次数,即前面已排好的元素数
          i := i+1
        }
      }
      //最后将 未排的首元素 与 分界点交换,分界点左边都小于分界点,分界点右边都大于分界点
      swap A[i] with A[r]
     
      // i就是那个分界点的位置
      return i
    
    

    上面伪代码的实现图例如图:

    排序算法名名是否为原地排序算法是否为稳定排序算法时间复杂度空间复杂度
    冒泡排序 O(n2) O(1)
    插入排序 O(n2) O(1)
    选择排序× O(n2) O(1)
    归并排序× O(nlogn) O(n)
    快速排序× O(nlogn) O(1)

    TOP