算法导论快速排序之python和ｃ++实现

１．快速排序

快速排序是一种比较快的排序算法，其主要思想是：

具体思想不再赘述。下面给出具体代码实现。

２．python3实现

#quick sort
#python3
#Yanglin Tu


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


def quicksort(arr, p, r):
    if p < r:
        q = partition(arr, p, r)
        quicksort(arr, p, q-1)
        quicksort(arr, q+1, r)


def main():
    list_a = [20, 5, 7, 1, 66, 47, 5, 18]
    print(list_a)
    length = len(list_a)
    quicksort(list_a, 0, length-1)
    print(list_a)


if __name__ == '__main__':
 	main()

３．Ｃ＋＋实现

//quick sort
//C++
//Yanglin Tu
#include <iostream>
using namespace std;

void swap(int &a,int &b){
    int temp;
    temp = a;
    a = b;
    b = temp;
}
int partition(int arr[],int p,int r){
    int x,i;
    x = arr[r];
    i = p-1;
    for (int j=p;j<r;j++){
        if(arr[j]<=x){
            int temp;
            i += 1;
            swap(arr[j],arr[i]);
        }
    }
    swap(arr[i+1],arr[r]);
    return i+1;
}
void quicksort(int arr[],int p,int r){
    if (p<r){
        int q = partition(arr,p,r);
        quicksort(arr,p,q-1);
        quicksort(arr,q+1,r);
    }
}
int main(){
    int i;
    int list_a[] = {20, 5, 7, 1, 66, 47, 5, 18};
    int length = sizeof(list_a) / sizeof(int);
    for (i = 0; i < length; i++)
        cout << list_a[i] << '\t';
    cout << endl;
    quicksort(list_a, 0, length - 1);
    for (i = 0; i < length; i++)
        cout<< list_a[i] << '\t';
    cout << endl;
    return 0;
}

４．快速排序的时间复杂度为O(nlgn)

５．快速排序的随机化版本

python3

# quick sort random
# python3
# Yanglin Tu
import random

def partition(arr, p, r):
    x = arr[r]
    i = p - 1
    for j in range(p, r):
        if arr[j] <= x:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[r] = arr[r], arr[i + 1]
    return i + 1
def randomized_partition(arr,p,r):
    i = random.randint(p, r)
    arr[i],arr[r] = arr[r],arr[i]
    return partition(arr,p,r)


def randomized_quicksort(arr, p, r):
    if p < r:
        q = randomized_partition(arr, p, r)
        randomized_quicksort(arr, p, q - 1)
        randomized_quicksort(arr, q + 1, r)


def main():
    list_a = [20, 5, 7, 1, 66, 47, 5, 18]
    print(list_a)
    length = len(list_a)
    randomized_quicksort(list_a, 0, length - 1)
    print(list_a)


if __name__ == '__main__':
    main()

c++

//quick sort random
//C++
//Yanglin Tu
#include <iostream>
#include <ctime>
using namespace std;

void swap(int &a, int &b)
{
    int temp;
    temp = a;
    a = b;
    b = temp;
}
int partition(int arr[], int p, int r)
{
    int x, i;
    x = arr[r];
    i = p - 1;
    for (int j = p; j < r; j++)
    {
        if (arr[j] <= x)
        {
            int temp;
            i += 1;
            swap(arr[j], arr[i]);
        }
    }
    swap(arr[i + 1], arr[r]);
    return i + 1;
}
int randomized_partition(int arr[], int p, int r)
{
    srand((unsigned)time(NULL));
    int i = (rand() % (r - p + 1)) + p;
    swap(arr[i], arr[r]);
    return partition(arr, p, r);
}
void randomized_quicksort(int arr[], int p, int r)
{
    if (p < r)
    {
        int q = randomized_partition(arr, p, r);
        randomized_quicksort(arr, p, q - 1);
        randomized_quicksort(arr, q + 1, r);
    }
}
int main()
{
    int i;
    int list_a[] = {20, 5, 7, 1, 66, 47, 5, 18};
    int length = sizeof(list_a) / sizeof(int);
    for (i = 0; i < length; i++)
        cout << list_a[i] << '\t';
    cout << endl;
    randomized_quicksort(list_a, 0, length - 1);
    for (i = 0; i < length; i++)
        cout << list_a[i] << '\t';
    cout << endl;
    return 0;
}