文档章节

快速排序

kimiz
 kimiz
发布于 2015/02/24 19:57
字数 268
阅读 143
收藏 11
#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.



© 著作权归作者所有

共有 人打赏支持
kimiz
粉丝 1
博文 17
码字总数 3593
作品 0
苏州
程序员
加载中

评论(1)

sinpo
sinpo
哈哈,大过年的都在写代码!佩服啊!!
常用的简单排序算法集合(更新中)

/** 冒泡排序 /public static void Bubble_Sort(int[] a) {for (int i = 0; i < a.length - 1; i++) {for (int j = 0; j < a.length - i - 1; j++) {if (a[j] > a[j + 1]) {a[i] = a[i] + a[......

维特的烦恼
2014/04/26
0
1
每天学习一点儿算法--快速排序

快速排序是一种常用的优雅的排序算法,它使用分而治之的策略。 那么分而治之(D&C)是一种怎样的策略呢? 分而治之 分而治之(D&C)的要点只有两个: 找出简单的基线问题 确定如何缩小问题的...

爱吃西瓜的番茄酱
01/11
0
0
快速排序详解 Java实现

一、快速排序的优缺点 对一个东西,首先要讲他的利与弊,才知道怎么使用它。快速排序适用于各种不同的输入数据且在一般应用中比其他排序都要快得多。快速排序引人注目的特点包括它是原地排序...

小车车
2016/09/03
49
0
快速排序算法QuickSort

1.说明 快速排序法(quicksort)是目前所公认最快的排序方法之一(视解题的对象而定),虽然快速排序法在最差状况下可以达O(n2),但是在多数的情况下,快速排序法的效率表现是相当不错的。快...

嗯哼9925
2017/12/14
0
0
排序——快速排序法

一、快速排序法概念 快速排序(Quick Sort)法是对冒泡排序的一种改进,其基本思想是:通过一遍排序将需要排序的数据划分成两部分,使其中一部分数据比另一部分数据小,然后再分别对这两部分...

翼动动空
2016/06/06
1K
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Go语言_通神之路(2)

1、包 每个Go程序都是由包构成,从main包开始运行,就是我上一篇讲到的,都是从main函数开始执行,但是必须在main包下面! package mainimport ( "fmt" "math/rand")func ...

木九天
昨天
1
0
51.php-fpm的pool 慢日志 open_basedir 进程管理

12.21 php-fpm的pool 12.22 php-fpm慢执行日志(测试时报错) 12.23 open_basedir 12.24 php-fpm进程管理 12.21 php-fpm的pool: php-fpm里的pool也叫池子,咱们之前加入过www的配置,这个w...

王鑫linux
昨天
0
0
java内存模型概述

1、Java虚拟机运行时数据分区图 程序计数器:线程私有,是一块较小的内存空间,它是当前线程所执行的字节码文件的行号指示器 java虚拟机栈:线程私有,其生命周期与线程相同,这也就是我们平...

京一
昨天
0
0
shell学习之test语法

因为if-then语句不能测试退出状态码之外的条件,所以提供了test, 如果test命令中列出的条件成立,test命令就会退出并返回退出状态码0;如果条件不成立,test命令就会退出并返回非零的退出状态...

woshixin
昨天
0
0
openJDK之如何下载各个版本的openJDK源码

如果我们需要阅读openJDK的源码,那么需要下载,那么该去哪下载呢? 现在JDK已经发展到版本10了,11已经处于计划中,如果需要特定版本的openJDK,它们的下载链接在哪呢? 1.openJDK的项目 链接...

汉斯-冯-拉特
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部