数据结构_排序⑧快速排序

2019-08-15 0 条评论 78 次阅读 0 人点赞

快速排序

  • hoare版本
  • 挖坑法
  • 前后指针版本
    空间: 空间可以复用 最大的递归调用链–> logN
    时间: N * logN
    序列有序 时间效率最差–> N^2

快速排序

void QuickSort(int* a, int left, int right){
    if(left >= right)
        return;
        //小区间优化: 小区间不再调用递归
    else if(right - left + 1 < 5){
        InsertSort(a + left, right - left + 1);
    }else{
        int mid = PartSort(a, left, right);
        QuickSort(a, left, mid - 1);
        QuickSort(a, mid + 1, right);
    }
}

三数取中对快排的三种方法进行优化

//三数取中法
int getMid(int* a, int left, int right){
    int mid = left + (right - left) / 2;
    if(a[mid] > a[left]){
        if(a[mid] < a[right]){
            return mid;
        }else{
            //mid >left, right
            if(a[left] > a[right]){
                return left;
            }else{
                return right;
            }
        }
    }else{
        //mid <= left
        if(a[left] < a[right]){
            return left;
        }else{
            //left >= right, mid
            if(a[mid] > a[right])
                return mid;
            else
                return right;
        }
    }
}

1.hoare版本

//快排的一次排序:确定基准值的位置
int PartSort(int* a, int left, int right){
    int mid = getMid(a, left, right);
    Swap(&a[mid], &a[left]);

    int key = a[left];
    int start = left;
    //寻找大小元素交换
    while(left < right){
        //先从右边找小于key的值
        while(left < right && a[right] >= key)
            --right;
        //从左边找大于key的值
        while(left < right && a[left] <= key)
            ++left;
        Swap(&a[left], &a[right]);
    }
    //key的位置确定 : left right 相遇的位置
    Swap(&a[start], &a[left]);
    return left;
}

2. 挖坑法

int Dig(int* a, int left, int right){
    int mid = getMid(a, left, right);
    Swap(&a[mid], &a[left]);
    int key = a[left];
    while (left < right){
        //从右边找小
        while (left > right && a[right] >= key){
            --right;
        }
        a[left] = a[right];
        //从左边找大的
        while (left < right && a[right] <= key)
            ++left;
        //填坑
        a[right] = a[left];
    }
    //存放key
    a[left] = key;
    return left;
}

3.前后指针法

int PrevCurPointer(int* a, int left, int right){
    int mid = getMid(a, left, right);
    Swap(&a[mid], &a[left]);

    //最后一个小于key的位置
    int prev = left;
    //下一个小于key的位置
    int cur = left + 1;
    int key = a[left];
    while (cur <= right){
        //如果下一个小于key的位置与上一个小于key的位置不连续
        //说明中间有大于key的值, 进行交换, 大-->向后移动, 小<--向前移动
        if(a[cur]< key && ++prev != cur){//不连续
            Swap(&a[prev], &a[cur]);
        }
        ++cur;
    }
    Swap(&a[prev], &a[left]);
    return prev;
}

快速排序非递归

stack.h

#include <stdio.h>
#include <assert.h>
#include <malloc.h>

typedef int STDatatype;
typedef struct Stack{
    STDatatype* _a; //数组指针
    size_t _top;
    size_t _capacity;
}Stack;

void StackInit(Stack* st);
void StackDestory(Stack* st);

void StackPush(Stack* st, STDatatype x);
void StackPop(Stack* st);

STDatatype StackTop(Stack* st);
int StackEmpty(Stack* st);
size_t StackSize(Stack* st);

QuickSortNor.c

void QuickSortNoR(int* a, int left, int right){//typedef int STDatatype
    Stack st;
    StackInit(&st);
    if(left < right){
        StackPush(&st, right);
        StackPush(&st, left);
    }
    while (StackEmpty(&st) == 0){
        int begin = StackTop(&st);
        StackPop(&st);
        int end = StackTop(&st);
        StackPop(&st);
        //划分当前区间
        int mid = PrevCurPointer(a, begin, end);
        //划分左右子区间
        if(begin < mid - 1){
            StackPush(&st, mid - 1);
            StackPush(&st, begin);
        }
        if(mid + 1 < end){
            StackPush(&st, end);
            StackPush(&st, mid + 1);
        }
    }
}

L_KingMing

这个人太懒什么东西都没留下

文章评论(0)