文档章节

快速排序

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

没有更多内容

加载失败,请刷新页面

加载更多

fabric增删改查Mac

备份1.3版本,重新下载1.1版本到fabric文件夹 /opt/gopath/src/github.com/hyperledger/fabric -> /opt/gopath/src/github.com/hyperledger/fabric1.3 新建/opt/gopath/src/github.com/hype......

八戒八戒八戒
18分钟前
2
0
盘点愚人节各大网站彩蛋,谁最爱恶搞?

如今的愚人节俨然已是各品牌宣传了一个重要节日,同时,也成为了各大互联网科技企业凑热闹,比拼创意和策划的节日。跟小编一起看看有哪些有趣的策划吧! Google地图变成吃豆人游戏 每年愚人节...

临江仙卜算子
42分钟前
3
0
Java7/8 中的 HashMap 和 ConcurrentHashMap 全解析

本文分析的是源码,所以至少读者要熟悉它们的接口使用,同时,对于并发,读者至少要知道 CAS、ReentrantLock、UNSAFE 操作这几个基本的知识,文中不会对这些知识进行介绍。Java8 用到了红黑树...

java菜分享
42分钟前
3
0
玩手机与做实验

看过这样一个故事:说的是在二十世纪二十年代初的一个深夜,担任英国剑桥大学卡文迪许实验室主任的卢瑟福来实验室检查,发现一位学生还在做实验。卢瑟福就问他:“你上午做什么了?”学生回答...

Bob2100
今天
5
0
Kafka流式处理

Kafka Streams 初识流式处理 什么是数据流 数据流(也叫事件流)是无边界数据集的抽象表示。无边界意味着无限和持续增长。无边界数据集之所以是无限的,是因为随着时间的推移,新记录会不断加...

东都大狼狗
今天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部