算法排序之归并排序和快速排序

归并排序和快速排序用的都是分治的思想,用递归的编程技巧来实现.咱们先来看归并排序.

归并排序

归并排序的核心思想就是,如果要排序一个数组,我们先从中间把数组分成两部分,分别对两部分排序,然后把排好序的两部分再合并.

归并排序的代码:

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]

  }

}

归并排序的性能分析:

1,归并排序是稳定的排序算法

2.归并排序的时间复杂度非常稳定,不管是最好情况,还是最坏情况,平均情况,时间复杂度都是O(nlogn)

3.归并排序的空间复杂度是O(n)

快速排序

快速排序的思想:如果要排序数组中下标从p到r的一组数据,我们选择p到r中的任意一点数据作为pivot(分区点).我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间数据就被分成了三个部分,前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot的

实现代码:

// 快速排序，A 是数组，n 表示数组的大小

quick_sort(A, n) {

  quick_sort_c(A, 0, n-1)

}

// 快速排序递归函数，p,r 为下标

quick_sort_c(A, p, r) {

  if p >= r then return

  q = partition(A, p, r) // 获取分区点

  quick_sort_c(A, p, q-1)

  quick_sort_c(A, q+1, r)

}

如果这样实现的话,空间复杂度就不是O(1),那么快排就不是原地排序算法了,如果让他是原地排序,可以这样.

partition(A, p, r) {

  pivot := A[r]

  i := p

  for j := p to r-1 do {

    if A[j] < pivot {

      swap A[i] with A[j]

      i := i+1

    }

  }

  swap A[i] with A[r]

  return I

归并排序和快速排序的区别

1,快排是原地,不稳定的排序算法,时间复杂度为O(nlogn)