说明在快速排序法(一)中,每次将最左边的元素设为轴,而之前曾经说过,快速排序法的加速在于轴的选
择,在这个例子中,只将轴设定为中间的元素,依这个元素作基准进行比较,这可以增加快速排序法的效率。
解法在这个例子中,取中间的元素s作比较,同样的先得右找比s大的索引i,然后找比s小的索引
j,只要两边的
索引还没有交会,就交换 i与 j的元素值,这次不用再进行轴的交换了,因为在寻找交换的过程中,轴位置的元
素也会参与交换的动作,例如:41
24
76
11
45
64
21
69
19
36
首先left为0,right为9,(left+right)/2
= 4(取整数的商),所以轴为索引4的位置,比较的元素是
45,您从左往右找比45大的,往从右往左找比45小的进行交换:
41 24 76* 11
[45] 64 2169 19 36*
41 24 36 11
45* 64 21 69 19* 76
41 24 36 11
19 64* 21* 69 45 76
[41 24 36 11 19 21] [64 69 45 76]
完成以上之后,再分别对左边括号与右边括号的部份进行递归,如此就可以完成排序的目的。
#include <stdio.h>
#include <stdlib.h>
#include <time.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] = {0};
int i, num;
srand(time(NULL));
printf("排序前:");
for(i = 0; i < MAX; i++)
{
number[i] = rand() % 100;
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+right)/2];
i = left - 1;
j = right + 1;
while(1)
{
while(number[++i] < s) ; // 向右找
while(number[--j] > s) ; // 向左找
if(i >= j)
break;
SWAP(number[i], number[j]);
}
// 对左边进行递归
quicksort(number, left, i-1);
// 对右边进行递归
quicksort(number, j+1, right);
}
}
//结果测试
分享到:
相关推荐
void qsort(int arr[],int left,int right) //qsort()函数实现快速排序,并且是递归调用,而且,递归调用qsort()函数本身两次,因为要对中值两边的 { //部分分别进行排序。arr是待排序的数组名,left是排序的左边界,...
在快速排序法(一)中,每次将最左边的元素设为轴,而之前曾经说过,快速排序法的加速在于轴的选择,在这个例子中,只将轴设定为中间的元素,依这个元素作基准进行比较,这可以增加快速排序法的效率。
算法的实验,背包问题,二分搜索_快速排序_背包问题,若有兴趣可以下载使用。
本资源包括一份分治法算法分析文档,4份Java源程序,包括二分查找、归并排序、快速排序、比赛日程安排。
常见经典排序算法(C语言)1希尔排序 二分插入法 直接插入法 带哨兵的直接排序法 冒泡排序 选择排序 快速排序 堆排序.docx
Problem Description ...第二行输入n个整数。 Output Description 输出排序后的整数,每个整数之间以一个空格分隔。注意:最后一个整数后面没有空格。 Sample Input 6 5 2 4 6 1 3 Sample Output 1 2 3 4 5 6
算法分析第二单元员 分治法的学习 中的经典问题3 也叫做归并排序
快速排序时目前比较的好的排序方法,相比较的别排序法,例如冒泡法,选择法等等。
快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试,包括像腾讯,微软等知名IT公司都喜欢考这个,还有大大小的...
直接插入、折半插入、冒泡、快速、简单选择等排序方法 用c语言实现 代码运行正常 不会有任何的问题
排序 桶 快速 冒泡
快速排序法(二) 快速排序法(三) 合并排序法 基数排序法 � 搜寻 循序搜寻法(使用卫兵) 二分搜寻法(搜寻原则的代表) 插补搜寻法 费氏搜寻法 � 矩阵 稀疏矩阵 多维矩阵转一维矩阵 上三角、下三角...
实现数据的折半插入排序、冒泡排序、快速排序和二路归并排序。 输入实例: 请输入待排序数据数目: 3 请输入待排序数据: 23,6,45 输出示例: 折半插入排序: 比较次数 移动元素次数 排序结果 6,23,45。
以从小到大排序为例,选择排序是从某一列数字当中选出最小的数字与第一个位置交换,在从第二个数字开始寻找第二小的数字与第二个位置交换,以此类推,直至最后一个数字交换完毕,排序完成
1)比较范围:直接插入排序、冒泡法排序、简单选择排序、快速排序1(自己实现)、快速排序2(调用STL)、归并排序。 2)比较指标:a)关键字操作次数(比较次数和移动次数之和),b)排序时间。每个指标采用多次重复...
分治法排序 归并排序与二分查找 算法课课件
这三个程序本人已经上机调试过,没错误,是C++编写的,经过老师审核过的,值得一下
不过,一路、二路归并排序、不平衡二叉树排序的速度均比冒泡排序快,且具有稳定性,但速度不及堆排序、快速排序。冒泡排序是经过n-1趟子排序完成的,第i趟子排序从第1个数至第n-i个数,若第i个数比后一个数大(则...
各种经典算法(总有一款你喜欢),河內塔 費式數列 巴斯卡三角形 三色棋 老鼠走迷官(一) 老鼠走迷官(二) 騎士走棋盤 ...快速排序法(二) 快速排序法(三) 合併排序法 基數排序法 。。。
某个二维数组存放了一系列的字符串,试利用排序的一些算法(如插入、冒泡、快速排序等)例如:二维数组的字符串如下: char s[][20]={“while”,”if”,“else”,”do”,“for”,”switch”,“case”,};