文档章节

快速排序

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

没有更多内容

加载失败,请刷新页面

加载更多

Spring的Resttemplate发送带header的post请求

private HttpHeaders getJsonHeader() { HttpHeaders headers = new HttpHeaders(); MediaType type = MediaType.parseMediaType("application/json; charset=UTF-8"); ......

qiang123
昨天
1
0
Spring Cloud Gateway 之 Only one connection receive subscriber allowed

都说Spring Cloud Gateway好,我也来试试,可是配置了总是报下面这个错误: java.lang.IllegalStateException: Only one connection receive subscriber allowed. 困扰了我几天的问题,原来...

ThinkGem
昨天
23
0
学习设计模式——观察者模式

1. 认识观察者模式 1. 定义:定义对象之间一种一对多的依赖关系,当一个对象状态发生变化时,依赖该对象的其他对象都会得到通知并进行相应的变化。 2. 组织结构: Subject:目标对象类,会被...

江左煤郎
昨天
1
0
emoji

前言:随着iOS系统版本的升级,对原生emoji表情的支持也越来越丰富。emoji表情是unicode码中为表情符号设计的一组编码,当然,还有独立于unicode的另一套编码SBUnicode,在OS系统中,这两种编...

HeroHY
昨天
2
0
rabbitmq学习(二)

生产者消费者初级案列 ChannelUtils package com.hensemlee.rabbitmq;import com.rabbitmq.client.Channel;import com.rabbitmq.client.Connection;import com.rabbitmq.client.Connecti......

hensemlee
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部