首页 > 编程语言 > 详细

简单实现快速排序

时间:2021-01-06 22:26:12      阅读:31      评论:0      收藏:0      [点我收藏+]

几个要点

1 当对小数组排序时,使用插入排序

2 使用 select 函数,选择较好的中心点

3 i 或 j 遇到与中心点相同的数时,也要停下。换来的好处是可以让右面的中心点作为 i 的哨兵

简单实现

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define size 100


void isort(int t[], int length)
{
    int i, j;
    int tmp;
    for(i = 1; i < length; i++) {
        tmp = t[i];
        for(j = i;j > 0; j--) {
            if(t[j-1] > tmp)            // 是与 tmp 比较 而不是 t[j]
                t[j] = t[j-1];
            else
                break;
        }
        t[j] = tmp;
    }
}

void swap(int &a, int &b){
    int tmp = a;
    a = b;
    b = tmp;
}


int select(int t[], int start, int end)
{
    int mid = (start + end) / 2;
    if(t[start] > t[mid])
        swap(t[start], t[mid]);
    if(t[start] > t[end])
        swap(t[start], t[end]);
    if(t[mid] > t[end])
        swap(t[mid], t[end]);
    swap(t[mid], t[end-1]);
    return t[end-1];
}


void msort(int t[], int length)
{
    int left = 0;
    int right = length - 1;
    int watershed;
    if(length <= 4) {
        isort(t, length);
        return ;
    }    
    watershed = select(t, left, right);
    int i, j;
    i = 0;
    j = right - 1;
    while(i < j) {
        while(t[++i] < watershed) {}        //i 会在大于等于 watershed 的地方停下
        while(t[--j] > watershed) {}        //j 会在小于等于 watershed 的地方停下
        if(i < j)
            swap(t[i], t[j]);
    }
    swap(t[i], t[right - 1]);
    msort(t, i + 1);
    msort(t + i + 1, length -i - 1);
}


int main()
{
    time_t seed;
    int n[size];

    seed = time(0);
    srandom(seed);

    for(int i = 0; i < size; i++) {
        n[i] = random()%1000;
    }
    msort(n, size);
    for(int i = 0; i < size; i++) 
        printf("%d ",n[i]);
    printf("\n");
    return 0;
}

 

简单实现快速排序

原文:https://www.cnblogs.com/sau-autumnwind/p/14243485.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!