（转）排序算法（3） 快速排序

转载至：https://blog.csdn.net/man_sion/article/details/70138747?utm_source=copy

 快速排序的算法是基于分治策略的另一个排序算法。

 该算法的基本思想是:

• 1.先从数列中取出一个数作为基准数，记为x。
• 2.分区过程，将不小于x的数全放到它的右边，不大于x的数全放到它的左边。（这样key的位置左边的没有大于key的，右边没有小于key的，只需对左右取区间排序即可）
• 3.再对左右区间重复第二步，直到各区间只有一个数。

 快排目前有两类实现算法，第一种是标准算法，第二种是两头交换法。总的思想与上面三步一样，在细节处理上有一些差异。

挖坑法

标准算法采用的思想是挖坑填坑的思想：
以一个数组作为示例，取区间第一个数为基准数。

0	1	2	3	4	5	6	7	8	9
72	6	57	88	60	42	83	73	48	85

初始时，i = 0; j = 9; X = a[i] = 72
由于已经将a[0]中的数保存到X中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。
从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8];
i++; 这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数，当i=3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3];
j--;

数组变为：

0	1	2	3	4	5	6	7	8	9
48	6	57	42	60	72	83	73	88	85

可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。

对挖坑填数进行总结
1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。
2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。

代码实现：

package sort

func quickSort(array []int) {
    x := array[0]

    i := 0
    j := len(array) - 1

    for {
        if i >= j {
            break
        }

        for {
            if i >= j {
                break
            }
            if array[j] >= x {
                j--
            }
        }
        if j > i {
            array[i] = array[j]
        }
        for {
            if i >= j {
                break
            }
            if array[i] <= x {
                i++
            }
        }
        if j > i {
            array[j] = array[i]
        }
    }
    array[i] = x
}

func quickSort2(array []int, left, right int) {
    i := left
    j := right
    x := array[i]
    for {
        if i >= j {
            break
        }

        for {
            if i >= j {
                break
            }
            if array[j] >= x {
                j--
            }
        }
        if j > i {
            array[i] = array[j]
        }
        for {
            if i >= j {
                break
            }
            if array[i] <= x {
                i++
            }
        }
        if j > i {
            array[j] = array[i]
        }
    }
    array[i] = x
    quickSort2(array, left, i)
    quickSort2(array, i+1, right)

}

---

左右指针法

选取一个关键字(key)作为枢轴，一般取整组记录的第一个数/最后一个，这里采用选取序列最后一个数为枢轴。
设置两个变量left = 0;right = N - 1;
从left一直向后走，直到找到一个大于key的值，right从后至前，直至找到一个小于key的值，然后交换这两个数。
重复第三步，一直往后找，直到left和right相遇，这时将key放置left的位置即可。

qianhou.png

代码实现：

// quickSort3 左右指针法
func quickSort3(array *[]int, i, j int) {
    left := i
    right := j
    key := (*array)[right]

    for {
        if left >= right {
            break
        }
        for {
            if left >= right || (*array)[left] > key {
                break
            }
            left++
        }
        for {
            if left >= right || (*array)[right] < key {
                break
            }
            right--
        }
        temp := (*array)[left]
        (*array)[left] = (*array)[right]
        (*array)[right] = temp
    }
    (*array)[left] = key
    quickSort3(array, i, left)
    quickSort3(array, left+1, j)
}

---

前后指针法

定义变量cur指向序列的开头，定义变量pre指向cur的前一个位置。
当array[cur] < key时，cur和pre同时往后走，如果array[cur]>key，cur往后走，pre留在大于key的数值前一个位置。
当array[cur]再次 < key时，交换array[cur]和array[pre]。

通俗一点就是，在没找到大于key值前，pre永远紧跟cur，遇到大的两者之间机会拉开差距，中间差的肯定是连续的大于key的值，当再次遇到小于key的值时，交换两个下标对应的值就好了。

带着这种思想，看着图示应该就能理解了。

前hou.png

代码实现：

// 前后指针法
func quickSort4(array *[]int, i, j int) {
    left := i
    right := j
    if left < right {
        key := (*array)[right]
        cur := left
        pre := cur - 1
        for {
            if cur >= right {
                break
            }
            for {
                if (*array)[cur] >= key || (pre+1) != cur { //如果找到小于key的值，并且cur和pre之间有距离时则进行交换。注意两个条件的先后位置不能更换，可以参照评论中的解释
                    pre = pre + 1
                    temp := (*array)[cur]
                    (*array)[cur] = (*array)[pre]
                    (*array)[pre] = temp
                }
            }
            cur++
        }
        pre = pre + 1
        temp := (*array)[pre]
        (*array)[pre] = (*array)[right]
        (*array)[right] = temp

        quickSort3(array, i, pre)
        quickSort3(array, pre+1, j)
    }

}

---

快速排序的优化

 首先快排的思想是找一个枢轴，然后以枢轴为中介线，一遍都小于它，另一边都大于它，然后对两段区间继续划分，那么枢轴的选取就很关键。

1. 三数取中法
   上面的代码思想都是直接拿序列的最后一个值作为枢轴，如果最后这个值刚好是整段序列最大或者最小的值，那么这次划分就是没意义的。
   所以当序列是正序或者逆序时，每次选到枢轴都是没有起到划分的作用。快排的效率会极速退化。
   所以可以每次在选枢轴，在序列的第一，中间，最后三个值里面选一个中间值出来作为枢轴，保证每次划分接近均等。

2.直接插入
由于是递归程序，每一次递归都要开辟栈帧，当递归到序列里的值不是很多时，我们可以采用直接插入排序来完成，从而避免这些些栈帧的消耗。

---

非递归实现

递归的算法主要是在划分子区间，如果要非递归实现快排，只要使用一个栈来保存区间就可以了。
一般将递归程序改成非递归首先想到的就是使用栈，因为递归本身就是一个压栈的过程。

// quickSort5 快速排序非递归（用栈来实现遍历区间）
func quickSort5(array *[]int, i, j int) {
    if i > j {
        return
    }
    stack := NewStack()
    stack.Push(i)
    stack.Push(j)

    for {
        if stack.Empty() {
            break
        }
        right := stack.Pop().(int)
        left := stack.Pop().(int)

        if left < right {
            mid := quickSort(array, left, right)
            // 左区间
            stack.Push(i)
            stack.Push(mid)
            // 右区间
            stack.Push(mid + 1)
            stack.Push(j)
        }

    }

}


// 挖坑法
func quickSort(array *[]int, i, j int) int {
    x := (*array)[i]

    for {
        if i >= j {
            break
        }

        for {
            if i >= j {
                break
            }
            if (*array)[j] >= x {
                j--
            }
        }
        if j > i {
            (*array)[i] = (*array)[j]
        }
        for {
            if i >= j {
                break
            }
            if (*array)[i] <= x {
                i++
            }
        }
        if j > i {
            (*array)[j] = (*array)[i]
        }
    }
    (*array)[i] = x

    return i
}