LaneBlog

蝼蚁虽小,也有梦想

PHP Socket服务 | PHP微信开发框架 | 开源博客

算法三:快速排序

Clicks: 12656 Date: 2014-10-29 22:43:04 Power By 李轩Lane

    

快速排序,是最常用的排序算法,就是选择待排序的列表中的其中一个数字,作为基准数,然后把小于基准数的所有数字放到这个数的左边,大于这个数的所有数字放到基准数的右边。这个时候开始分为两部分,左边和右边。第一部分,在左边中选择一个数字作为基准数,把小于这个数字的放到这个数的左边,大于这个数的放到这个数的右边。第二部分,在右边中选择一个数字作为基准数,把小于这个数字的放到这个数的左边,大于这个数的放到这个数的右边。ok,很明显,递归!

快速排序的时间复杂度在最坏的情况下是O(N2),因为和冒泡排序一样,需要两两交换。平均情况下,快速排序的时间复杂度是O(NlogN)。

下面是C语言的代码

#include <stdio.h>

void quickSort(int left, int right, int *rank);

int main(){

    int i, j, num, score, tmp;

    printf("How many?\n");

    scanf("%d", &num);

    int rank[num];

    for(i=0; i<num; i++){

        printf("Enter Score:\n");

        scanf("%d", &score);

        //我们的试卷是0-100分的哦

        if(score<0 || score > 100){

            printf("Error");

            return 1;

        }

        rank[i] = score;

    }

    printf("Rank:\n");

    quickSort(0, num-1, rank);

    for(i=0; i<num; i++){

        printf("%d,", rank[i]);

    }

    return 0;

}

void quickSort(int left, int right, int *rank){

    if(left > right){

        return;

    }

    int i, j, t, tmp;

    i = left;

    j = right;

    t = rank[left];

    while(i!=j){

        while(rank[j]>=t && i<j)

            j--;

        while(rank[i]<=t && i<j)

            i++;

        if(i < j){

            tmp = rank[j];

            rank[j] = rank[i];

            rank[i] = tmp;

        }

    }

    rank[left] = rank[i];

    rank[i] = t;

    quickSort(left, i-1, rank);

    quickSort(i+1, right, rank);

}


Reply: weihd On 2014-11-01 20:22:12

very nice

回复

Reply: StevJaby On 2020-03-21 01:31:53

Priligy Venta https://apcialisle.com/# - online cialis Miglior Viagra Senza Ricetta <a href=https://apcialisle.com/#>Cialis</a> Viagra Requiere Receta Medica

回复

Reply: VassiGn On 2020-05-04 04:47:58

No Presription Finasteride https://abcialisnews.com/# - Cialis Where Can I Buy Discount Progesterone Medication Shop <a href=https://abcialisnews.com/#>Cialis</a> Levoxyl Pharm

回复

Reply: Launa On 2020-05-17 19:33:59

Wonderful post! We are linking to this great article on our site. Keep up the great writing.

回复

Add Comment
©2014 www.lanecn.com , All rights reserved. Power By Li Xuan.  京ICP备14005030号