2020-03-23

针对快速排序，双指针中有快慢指针法，和左右夹逼法。
快慢指针法，写法相对容易，不容易出错，而左右夹逼，写法的注意事项较多；
https://blog.csdn.net/qq_34557770/article/details/100690849
我感觉，他写的很好，针对swap ，由于python 一行就搞定了，而且还没有先后顺序，python 就不要再用个swap函数了。毕竟函数调用，压栈弹栈，也需要开销。
我一般习惯用最右边元素做基准，因为pyton range是左闭右开的；

#c 
public class QuickSort {
    public void quickSort(int[] nums, int left, int right) {
        if (left < right) {
            int partition = partition(nums, left, right);
            quickSort(nums, left, partition - 1);
            quickSort(nums, partition + 1, right);
        }
    }
 
    public int partition(int[] nums, int left, int right) {
        int start = left;
        int end = right;
        int target = nums[right];
        while (start < end) {
            while (start < end && nums[start] < target) {// it is  not <=
                start++;
            }
            while (start < end && nums[end] >= target) {
                end--;
            }
            swap(nums, start, end);
        }
        swap(nums, right, start);
        return start;
    }
 
    private void swap(int[] nums, int start, int end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
    }
}

#原文链接：https://blog.csdn.net/qq_34557770/article/details/100690849

再看看，这个的解法，左边为基准的
https://www.jianshu.com/p/2b2f1f79984e

def quick_sort(L):
    return q_sort(L, 0, len(L) - 1)

def q_sort(L, left, right):
    if left < right:
        pivot = Partition(L, left, right)

        q_sort(L, left, pivot - 1)
        q_sort(L, pivot + 1, right)
    return L

def Partition(L, left, right):
    pivotkey = L[left]

    while left < right:
        while left < right and L[right] >= pivotkey:
            right -= 1
        L[left] = L[right]
        while left < right and L[left] <= pivotkey:
            left += 1
        L[right] = L[left]

    L[left] = pivotkey
    return left

L = [5, 9, 1, 11, 6, 7, 2, 4]

print quick_sort(L)

针对分区函数

def pp(arr,left,r):
    temp=r
    key=arr[r]
    slow=left
    for fast in range(left,r):
        if arr[fast]<=key:
            arr[fast],arr[slow]=arr[slow],arr[fast]
            slow+=1
    arr[slow],arr[temp]=arr[temp],arr[slow]
    return slow

完整代码如下

# -*- coding: utf-8 -*-
"""
Spyder Editor

This is a temporary script file.
"""
def quick_sort(L):
    return q_sort(L, 0, len(L) - 1)

def q_sort(L, left, right):
    if left < right:
        pivot = Partition(L, left, right)

        q_sort(L, left, pivot - 1)
        q_sort(L, pivot + 1, right)
    return L


def Partition(arr, left, r):
    temp=r
    key=arr[r]
    slow=left
    for fast in range(left,r):
        if arr[fast]<=key:
            arr[fast],arr[slow]=arr[slow],arr[fast]
            slow+=1
    arr[slow],arr[temp]=arr[temp],arr[slow]
    return slow
L = [4,3,6,4,4,4,5, 9, 1, 11, 6,555, 7, 2, 4,4,4,4,4]

print (quick_sort(L))

def quick_sort(array, l, r):
    if l < r:
        q = partition(array, l, r)
        quick_sort(array, l, q - 1)
        quick_sort(array, q + 1, r)

def partition(array, l, r):
    x = array[r]
    i = l - 1
    for j in range(l, r):
        if array[j] <= x:
            i += 1
            array[i], array[j] = array[j], array[i]
    array[i + 1], array[r] = array[r], array[i+1]
    return i + 1

各种写法,从中可以看出，同是O（n）级别的函数，执行效率之间的差异。