文档章节

快速排序

Endroid
 Endroid
发布于 2013/09/30 16:55
字数 667
阅读 27
收藏 0
// 快速排序
// 基本思想:通过一趟排序将要排序的数据分割成独立的两部分,
// 其中一部分的所有数据都比另外一部分的所有数据都要小,
// 然后再按此方法对这两部分数据分别进行快速排序,
// 整个排序过程可以递归进行,以此达到整个数据变成有序序列。
/*
已知一组无序数据a[1]、a[2]、……a[n],需将其按升序排列。
首先任取数据a[x]作为基准。
比较a[x]与其它数据并排序,使a[x]排在数据的第k位,
并且使a[1]~a[k-1]中的每一个数据<a[x],a[k+1]~a[n]中的每一个数据>a[x],
然后采用分治的策略分别对a[1]~a[k-1]和a[k+1]~a[n]两组数据进行快速排序。
*/
#include <stdio.h>

void QUICKSORT(int arr[], int left, int right);
int  PARTITION(int arr[], int left, int right);
void EXCHANGE(int *a, int *b);
void printArray(int *a, int size);

void main()
{
	int arr[10] = {3,8,2,9,6,4,10,11,4,1};	// 排序,从小到大
	int a_size = sizeof(arr)/sizeof(arr[0]);
	
	printf("未排序的数组:\n");
	printArray(arr,a_size);
	printf("\n排序过程:\n");
	
	// 开始快速排序
	QUICKSORT(arr,0,9);
	
	// 排序结果:
	printf("\n排序后数组:\n");
	printArray(arr,a_size);
}

void QUICKSORT(int arr[], int left, int right)
{
	if(left < right) {
		int pos = PARTITION(arr, left, right);
		QUICKSORT(arr, left, pos - 1);	// 分治
		QUICKSORT(arr, pos + 1, right);
	}
}

int PARTITION(int arr[], int left, int right)
{
	int privot, low, high;
	privot = arr[left];  // 基准,数值不变,位置变换
    low = left;
    high = right;
	
	while(low < high)
    {
		while(arr[high] >= privot) // high从右向左找小于x的元素    
			high--;
		
		if(low < high)	// 找到小于x的记录就进行交换。
		{
			EXCHANGE(&arr[low],&arr[high]);
			printArray(arr,10);
			low++;
		}
		
		// 接着找寻左边的
		while(arr[low] < privot) // low从左向右找大于x的元素  
			low++;
		
		if(low < high)	// 找到大于x的记录则进行交换。
		{
			EXCHANGE(&arr[low],&arr[high]);
			printArray(arr,10);
			high--;
		}
    }

    return low; // 返回基准位置
}

void EXCHANGE(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void printArray(int *a, int size)
{
	int a_size = size;
	for(int k = 0; k< a_size; k++)
	{
		if( k  == a_size - 1)
			printf("%d", a[k]);
		else
			printf("%d, ", a[k]);
	}
	printf("\n");
}

执行结果: 

未排序的数组:
3, 8, 2, 9, 6, 4, 10, 11, 4, 1

排序过程:
1, 8, 2, 9, 6, 4, 10, 11, 4, 3
1, 3, 2, 9, 6, 4, 10, 11, 4, 8
1, 2, 3, 9, 6, 4, 10, 11, 4, 8
1, 2, 3, 8, 6, 4, 10, 11, 4, 9
1, 2, 3, 8, 6, 4, 9, 11, 4, 10
1, 2, 3, 8, 6, 4, 4, 11, 9, 10
1, 2, 3, 8, 6, 4, 4, 9, 11, 10
1, 2, 3, 4, 6, 4, 8, 9, 11, 10
1, 2, 3, 4, 4, 6, 8, 9, 11, 10
1, 2, 3, 4, 4, 6, 8, 9, 10, 11

排序后结果
1, 2, 3, 4, 4, 6, 8, 9, 10, 11
Press any key to continue

© 著作权归作者所有

Endroid
粉丝 8
博文 46
码字总数 68781
作品 0
深圳
程序员
私信 提问
常用的简单排序算法集合(更新中)

/** 冒泡排序 /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
140
1
每天学习一点儿算法--快速排序

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

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

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

小车车
2016/09/03
71
0
好程序员Java教程教你5分钟了解快速排序

好程序员Java教程教你5分钟了解快速排序,前言: 快速排序是面试中经常会问到的一种排序算法,对比其他一些排序算法,快速排序的平均时间相对较少。 快速排序思想介绍 快速排序使用了分治的思...

好程序员IT
06/21
38
0
快速排序算法QuickSort

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

嗯哼9925
2017/12/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

nginx学习笔记

中间件位于客户机/ 服务器的操作系统之上,管理计算机资源和网络通讯。 是连接两个独立应用程序或独立系统的软件。 web请求通过中间件可以直接调用操作系统,也可以经过中间件把请求分发到多...

码农实战
今天
5
0
Spring Security 实战干货:玩转自定义登录

1. 前言 前面的关于 Spring Security 相关的文章只是一个预热。为了接下来更好的实战,如果你错过了请从 Spring Security 实战系列 开始。安全访问的第一步就是认证(Authentication),认证...

码农小胖哥
今天
12
0
JAVA 实现雪花算法生成唯一订单号工具类

import lombok.SneakyThrows;import lombok.extern.slf4j.Slf4j;import java.util.Calendar;/** * Default distributed primary key generator. * * <p> * Use snowflake......

huangkejie
昨天
12
0
PhotoShop 色调:RGB/CMYK 颜色模式

一·、 RGB : 三原色:红绿蓝 1.通道:通道中的红绿蓝通道分别对应的是红绿蓝三种原色(RGB)的显示范围 1.差值模式能模拟三种原色叠加之后的效果 2.添加-颜色曲线:调整图像RGB颜色----R色增强...

东方墨天
昨天
11
1
将博客搬至CSDN

将博客搬至CSDN

算法与编程之美
昨天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部