说明快速排序法(quick sort)是目前所公认最快的排序方法之一,快速排序法的基本精神是在数列中找出适当
的轴心,然后将数列一分为二,分别对左边与右边数列进行排序,而影响快速排序法效率的正是轴心的选择。
这是第一个快速排序法版本,是在多数的教科书上所提及的版本,因为它最容易理解,
也最符合轴心分割与左右进行排序的概念,适合对初学者学习。
解法这边所介绍的快速演算如下:将最左边的数设定为轴,并记录其值为
令索引 i从数列左方往右方找,直到找到大于 s的数
令索引 j从数列右方往左方找,直到找到小于 s的数
如果 i >= j,则离开本循环
如果 i < j,则交换索引i与j两处的值
将左侧的轴与 j进行交换
对轴左边进行递归
对轴右边进行递归
透过以下演算法,则轴左边的值都会小于s,轴右边的值都会大于s,如此再对轴左右两边进行
递归,就可以对完成排序的目的,例如下面的实例,*表示要交换的数,[]表示轴:
[33] 65* 23 90 1 34 43 39 87 5*
[33]5 23* 90 1 34 43 39 87* 65
[33]5 23 90* 1* 34 43 39 87 65
[33]5 231 90 34 4339 87 65
[5] 23133 [90]34 4339 87 65
在上面的例子中,33左边的值都比它小,而右边的值都比它大,如此左右再进行递回至排序完成。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 10
#define SWAP(x,y) {int t; t = x; x = y; y = t;}
void quicksort(int[], int, int);
int main(void)
{
int number[MAX] = {33,65,23,90,1,34,43,29,87,5};
int i, num;
printf("排序前:");
for(i = 0; i < MAX; i++)
{
printf("%d ", number[i]);
}
quicksort(number, 0, MAX-1);
printf("\n排序后:");
for(i = 0; i < MAX; i++)
printf("%d ", number[i]);
printf("\n");
return 0;
}
//快速排序
void quicksort(int number[], int left, int right)
{
int i, j, s;
if(left < right)
{
s = number[left];
i = left;
j = right + 1;
while(1)
{
// 向右找
while(i + 1 < MAX && number[++i] < s) ;
// 向左找
while(j -1 > -1 && number[--j] > s) ;
if(i >= j)
break;
SWAP(number[i], number[j]);
}
number[left] = number[j];
number[j] = s;
// 对左边进行递归
quicksort(number, left, j-1);
// 对右边进行递归
quicksort(number, j+1, right);
}
}
//结果测试
分享到:
相关推荐
快速排序法(quick sort)是目前所公认最快的排序方法之一(视解题的对象而定),虽然快速排序法在最差状况下可以达O(n2),但是在多数的情况下,快速排序法的效率表现是相当不错的。 快速排序法的基本精神是在数列中...
使用快速排序法对一维数组进行排序,程序完全可以运行,方便大家学习
之前说过轴的选择是快速排序法的效率关键之一,在这边的快速排序法的轴选择方式更加快了快速排序法的效率,它是来自演算法名书 Introduction to Algorithms 之中。
这是一个用Java语言实现的快速排序算法,快速排序算法是根据分冶思想去实现的。
void qsort(int arr[],int left,int right) //qsort()函数实现快速排序,并且是递归调用,而且,递归调用qsort()函数本身两次,因为要对中值两边的 { //部分分别进行排序。arr是待排序的数组名,left是排序的左边界,...
一个快速排序法的例子 构建1亿的随机数,完整排序花时26秒左右
快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。 步骤为: 从数列中挑出一个元素,称为“基准”(pivot), 重新排序数列,所有比基准值小的元素摆放在基准前面...
java 快速排序 折半查找的界面实现 (递归与分治法)
一种快速的排序法—插入合并排序法一种快速的排序法—插入合并排序法
分治法的另外一种排序算法,快速排序。有注释,便于阅读,因为交换时使用的引用,暂时归为C++,C语言版稍后奉上。
使用快速排序算法实现对n个元素进行排序。 由文件input.txt提供输入数据,输出到文件output.txt中。
在快速排序法(一)中,每次将最左边的元素设为轴,而之前曾经说过,快速排序法的加速在于轴的选择,在这个例子中,只将轴设定为中间的元素,依这个元素作基准进行比较,这可以增加快速排序法的效率。
//如果两边扫描的下标交错,就停止(完成一次) //当左边部分有值(left),递归左半边 if(left) QuickSort (pData,left,j); //当右边部分有值(right>i),递归右半边 if(right>i) QuickSort (pData,i,right);...
分治法的应用,快速排序是其中一种。注释便于读者明白。
这是一个利用MFC界面做的快速排序法的实现
它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个...
快速排序算法是当前使用最多的排序算法之一,它的基本思想是分治法,选择一个划分元,将小于划分元的元素放在左边,将大于划分元的元素放在右边,针对左右子序列重复此过程,直到序列为空或者只有一个元素,这是基本...
Problem Description 使用插入排序算法对输入的n个整数,按照从小到大的...输出排序后的整数,每个整数之间以一个空格分隔。注意:最后一个整数后面没有空格。 Sample Input 6 5 2 4 6 1 3 Sample Output 1 2 3 4 5 6
递归求解(Conquer):通过递归对p..aq和aq+1..ar进行排序。 合并(Merge):由于对分解出的两个子序列的排序是就地进行的,所以在ap..aq和aq+1..ar都排好序后不需要执行...因此,快速排序法是分治法的经典应用实例之一。
在某些情况下,快速排序法法是最快的一种排序算法,并且它有很大的推广潜力