快速排序
博客专区 > kimiz 的博客 > 博客详情
快速排序
kimiz 发表于3年前
快速排序
  • 发表于 3年前
  • 阅读 138
  • 收藏 11
  • 点赞 0
  • 评论 1

腾讯云 技术升级10大核心产品年终让利>>>   

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

void swap(int *i, int *j);
int choose_pivot(int i, int j);
int partition(int list[], int m, int n);
void quicksort(int list[], int m, int n);
void display(int list[], const int n);
const int SIZE = 10;

int main()
{
    int list[SIZE];

    int i = 0;
    for (i = 0; i < SIZE; ++i) {
        list[i] = rand();
    }

    printf("the list before sorting is: \n");
    display(list, SIZE);

    quicksort(list, 0, SIZE-1);

    printf("the list after sorting is: \n");
    display(list, SIZE);

    return 0;
}

void swap(int *i, int *j)
{
    int temp;

    temp = *i;
    *i = *j;
    *j = temp;
}

int choose_pivot(int i, int j)
{
    return (i+j)/2;
}

int partition(int list[], int m, int n)
{
    int pivot;
    int pivotkey;

    pivot = choose_pivot(m, n);
    swap(&list[m], &list[pivot]);
    pivotkey = list[m];

    while (m < n) {
        while ( (m < n) && (list[n] >= pivotkey) )
            n--;
        if (m < n) {
            list[m++] = list[n];
        }

        while ( (m < n) && (list[m] < pivotkey) )
            m++;
        if (m < n) {
            list[n--] = list[m];
        }
    }
    list[m] = pivotkey;

    pivot = m;
    return pivot;
}
void quicksort(int list[], int m, int n)
{
    int pivot;
    if (m < n) {
        pivot = partition(list, m, n);
        quicksort(list, m, pivot-1);
        quicksort(list, pivot+1, n);
    }
}

void display(int list[], const int n)
{
    int i;
    for(i = 0; i < n; ++i) {
        printf("%d\t", list[i]);
    }
}


the list before sorting is:
41      18467   6334    26500   19169   15724   11478   29358   26962   24464
the list after sorting is:
41      6334    11478   15724   18467   19169   24464   26500   26962   29358

Process returned 0 (0x0)   execution time : 0.042 s
Press any key to continue.



共有 人打赏支持
粉丝 2
博文 17
码字总数 3593
评论 (1)
sinpo
哈哈,大过年的都在写代码!佩服啊!!
×
kimiz
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: