之前总以为自己已经掌握了快速排序,可是眼高手低,没有好好研究一下它是否是稳定的排序,以及涉及重复元素等问题,最近用到时总是出现小的bug,于是又潜心翻看《算法导论》,经过测试,写出一个正确的快速排序算法。
写正确关键在于paration函数:
(1)如果s<=k<=i,则有a[k]<=m(中枢元素)
(2)如果i+1<=k<=j-1,则有a[i]>m
(3)如果k=e,则有a[k]=x
变量s和e分别表示数组a的起始和结尾元素,i用于跟踪j,直到遇到>中枢元素m的值,此时a[i+1]>m,等待下次(如果存在)遇到<=中枢元素m的知,然后交换。
注意:在paration()函数中选择随机中枢元素时,必须基于当前s值(即在当前s上加上随机值)。
view plaincopy to clipboardprint?
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <time.h>
4 void quite_sort(int *,int,int);
5 int paration(int*,int,int);
6 void print(int*,int );
7 void swap(int*,int* );
8 int main()
9 {
10 int a[]={1,2,5,3,2,1,7,4};
11 quite_sort(a,0,7);
12 print(a,8);
13
14 //int b[]={9,9,8,8,7,7};
15 //quite_sort(b,0,5);
16 //print(b,6);
17
18 //int c[]={2,2,2,2};
19 //quite_sort(c,0,3);
20 //print(c,4);
21
22 }
23 void print(int *a,int len)
24 {
25 int i = 0;
26 for(;i<len;i++)
27 printf("%d ",a[i]);
28 printf("/n");
29 }
30 void quite_sort(int *a,int s,int e)
31 {
32 if(s<e)
33 {
34 int p = paration(a,s,e);
35 quite_sort(a,s,p-1);
36 quite_sort(a,p+1,e);
37 }
38 }
39 int paration(int *a,int s,int e)
40 {
41 int l = e-s+1;
42 srand(time(NULL));
43 int r = rand()%l+s;
44 swap(&a[r],&a[e]);
45 int m = a[e];
46 printf("aaa%d /n",r);
47
48 int i =s-1,j = s;
49 while(j<e)
50 {
51 if(a[j]<=m)
52 {
53 i++;
54 swap(&a[i],&a[j]);
55 }
56 j++;
57 }
58 swap(&a[e],&a[i+1]);
59 return i+1;
60 }
61 void swap(int *a,int *b)
62 {
63 int tmp = *a;
64 *a = *b;
65 *b = tmp;
66 }
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <time.h>
4 void quite_sort(int *,int,int);
5 int paration(int*,int,int);
6 void print(int*,int );
7 void swap(int*,int* );
8 int main()
9 {
10 int a[]={1,2,5,3,2,1,7,4};
11 quite_sort(a,0,7);
12 print(a,8);
13
14 //int b[]={9,9,8,8,7,7};
15 //quite_sort(b,0,5);
16 //print(b,6);
17
18 //int c[]={2,2,2,2};
19 //quite_sort(c,0,3);
20 //print(c,4);
21
22 }
23 void print(int *a,int len)
24 {
25 int i = 0;
26 for(;i<len;i++)
27 printf("%d ",a[i]);
28 printf("/n");
29 }
30 void quite_sort(int *a,int s,int e)
31 {
32 if(s<e)
33 {
34 int p = paration(a,s,e);
35 quite_sort(a,s,p-1);
36 quite_sort(a,p+1,e);
37 }
38 }
39 int paration(int *a,int s,int e)
40 {
41 int l = e-s+1;
42 srand(time(NULL));
43 int r = rand()%l+s;
44 swap(&a[r],&a[e]);
45 int m = a[e];
46 printf("aaa%d /n",r);
47
48 int i =s-1,j = s;
49 while(j<e)
50 {
51 if(a[j]<=m)
52 {
53 i++;
54 swap(&a[i],&a[j]);
55 }
56 j++;
57 }
58 swap(&a[e],&a[i+1]);
59 return i+1;
60 }
61 void swap(int *a,int *b)
62 {
63 int tmp = *a;
64 *a = *b;
65 *b = tmp;
66 }
关于paration的另一种写法如下:
但是这种写法非常容易出错,必须遵循:
(1)如果取中枢元素m=a[e](即结尾元素),必须保证先做low的自增操作,然后是high的自减操作。
(2)如果取中枢元素m=a[s](即起始元素),必须保证先做high的自减操作,然后是high的自增操作。(代码中所示)
否则将会出现错误。测试案例如3,3,3,1,5,2,4等。
view plaincopy to clipboardprint?
39 int paration(int *a,int s,int e)
40 {
41 int m = a[e];
42 int l = s;
43 int h = e;
44 while(l<h)
45 {
46 while(l<h && a[l]<=m)
47 l++;
48 swap(&a[l],&a[h]);
49 while(l<h && a[h]>=m)
50 h--;
51 swap(&a[h],&a[l]);
52
53 }
54 return l;
55 }
分享到:
相关推荐
数据结构——快速排序 数据结构——快速排序 数据结构——快速排序 数据结构——快速排序 数据结构——快速排序
舍伍德——快速排序源码报告和算法分析 有需要的朋友看下
/********************快排算法************************/ void quicksort(int A[],int p,int r) { int q; if(p) { q=partition(A,p,r); quicksort(A,p,q-1);... quicksort(A,q+1,r);.../************************...
算法与数据结构——快速排序
快速排序有很多不同的算法来解决,在此我是用C++来编写这个程序的,根据快速排序的算法思想,很容易将此问题解决。还可以运用非递归的方法解决,但是我不熟练。
#include #include class Array{ public: Array(int Size=150);//构造函数 ~Array() {delete[]T;}// 析构函数 //取数组长度 int qdivde(int low,int high); void print(); void exchange(int i,int j);...
快速排序 * 1.i=left,j=right,将基准数挖出形成第一个坑a[i]; * 2.j--由后向前找比它小的数,找到后挖出此数填前一个坑a[i]; * 3.i++由前向后找比它大的数,找到后挖出此数填到前一个坑a[j]中 * 4.以i为中线,...
NULL 博文链接:https://wojiaolongyinong.iteye.com/blog/1868188
数据结构课程设计 快速排序 两江大学出版社
课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
python快速排序(csdn)————程序
以从小到大排序为例,选择排序是从某一列数字当中选出最小的数字与第一个位置交换,在从第二个数字开始寻找第二小的数字与第二个位置交换,以此类推,直至最后一个数字交换完毕,排序完成
实例009——实现排序操作 实例009——冒泡排序操作 实例009——快速排序操作 实例009——插入排序操作 实例009——选择排序操作
本实验含有四部分内容——直接插入排序、希尔排序、选择排序、快速排序,在上述内容的基础上,将所有排序算法整合在一个程序中。学生可参考教材中的伪代码。鼓励学生自创新思路,新算法。
Python排序算法详解 Python排序算法——冒泡排序 Python排序算法——插入排序 Python排序算法——选择排序 Python排序算法——快速排序 Python排序算法——归并排序
(1) 首先产生包含 1,000,000 个随机数(数据类型可选整型或者浮点型)的数据文件 (2) 每次数据分割后产生两个新的进程(或线程)处理分割后的数据,每
设计一个负责排序的程序包,实现多种排序算法,至少包括插入排序、冒泡排序和快速排序算法。 内含代码和实验报告
冒泡排序实际上是将数据从右至左排序完成(从右至左、从大到小进行交换排序),而快速排序是将数据从左到右排序完成(从左至右、从小到大进行交换排序),虽然选择排序相对于冒泡排序将交换次数从O(n2)O(n^2)O(n2)...
四种排序算法,插入排序 折半排序 快速排序 冒泡排序,c语言编写,可执行
3、快速排序 4、简单选择排序 要求: 1、测试数据分成三类:正序、逆序、随机数据 2、对于这三类数据,比较上述排序算法中关键字的比较次数和移动次数(其 中关键字交换计为3次移动)。 3、对于这三类数据,...