快速排序法c语言,C语言快速排序算法问题
快速排序法c语言,C语言快速排序算法问题详细介绍
本文目录一览： C语言快速排序算法问题
快速排序法”使用的是递归原理，下面我结合一个例子来说明“快速排序法”的原理。首先给出一个数组{53，12，98，63，18，72，80，46， 32，21}，先找到第一个数--53，把它作为中间值，也就是说，要把53放在一个位置，使得它左边的值比它小，右边的值比它大。{21，12，32， 46，18，53，80，72，63，98}，这样一个数组的排序就变成了两个小数组的排序--53左边的数组和53右边的数组，而这两个数组继续用同样的方式继续下去，一直到顺序完全正确。
一般来说，冒泡法是程序员最先接触的排序方法，它的优点是原理简单，编程实现容易，但它的缺点就是--程序的大忌--速度太慢。
附上快速排序代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include
void quicksort(int a[],int left,int right)
{
int i,j,temp;
i=left;
j=right;
temp=a[left];
if(left>right)
return;
while(i!=j)
{
while(a[j]>=temp&&j>i)
j--;
if(j>i)
a[i++]=a[j];
while(a[i]<=temp&&j>i)
i++;
if(j>i)
a[j--]=a[i];
}
a[i]=temp;
quicksort(a,left,i-1);
quicksort(a,i+1,right);
}
void main()
{
int a[]={53,12,98,63,18,72,80,46,32,21};
int i;
quicksort(a,0,9);
/*排好序的结果*/
for(i=0;i<10;i++)
printf("%4d\n",a[i]);
}
菜鸟提问 c语言关于快速排序
R[j]^=R[i];
R[i]^=R[j];
R[j]^=R[i];
你的代码里面R[i]^，R[j]^从何而来？不理解，不好改。
快速排序作为c语言中速度最快的一种排序，肯定能处理数字相同的情况，而且快速排序肯定是用递归算法。你的问题是算法，这里有个带注释的快速排序，win-tc和Dev-c++下运行通过。
#include
#include
#define MAX 255
int R[MAX];
int Partition(int i,int j)
{/* 调用Partition(low，high)时，对R[low..high]做划分，*/
/* 并返回基准记录的位置 */
int pivot=R[i]; /* 用区间的第1个记录作为基准 */
while(i
<j)
{ /* 从区间两端交替向中间扫描，直至i=j为止 */
while(i
=pivot) /* pivot相当于在位置i上 */
j--; /* 从右向左扫描，查找第1个关键字小于pivot.key的记录R[j] */
if(i
<j) * 表示找到的r[j]的关键字<pivot.key
R[i++]=R[j]; /* 相当于交换R[i]和R[j]，交换后i指针加1 */
while(i
<j&&r[i]<=pivot) * pivot相当于在位置j上*
i++; /* 从左向右扫描，查找第1个关键字大于pivot.key的记录R[i] */
if(i
pivot.key */
R[j--]=R[i]; /* 相当于交换R[i]和R[j]，交换后j指针减1 */
}
R[i]=pivot; /* 基准记录已被最后定位*/
return i;
}
void Quick_Sort(int low,int high) /* 对R[low..high]快速排序 */
{ int pivotpos; /* 划分后的基准记录的位置 */
if(low
<high)
{/* 仅当区间长度大于1时才须排序 */
pivotpos=Partition(low,high); /* 对R[low..high]做划分 */
Quick_Sort(low,pivotpos-1); /* 对左区间递归排序 */
Quick_Sort(pivotpos+1,high); /* 对右区间递归排序 */
}
}
main()
{int i,n;
clrscr();
puts("Please input total element number of the sequence:");
scanf("%d",&n);
if(n<=0||n>MAX)
{ printf("n must more than 0 and less than %d.\n",MAX);
exit(0);
}
puts("Please input the elements one by one:");
for(i=1;i<=n;i++)
scanf("%d",&R[i]);
puts("The sequence you input is:");
for(i=1;i<=n;i++)
printf("%4d",R[i]);
Quick_Sort(1,n);
puts("\nThe sequence after quick_sort is:");
for(i=1;i<=n;i++)
printf("%4d",R[i]);
puts("\n Press any key to quit...");
getch();
}
#include
#include
void swap(int &a,int &b){ //交换两个数
int temp=a;
a=b;
b=temp;
}
void quicksort(int R[],int s,int t)
{
int i=s,j=t;
int temp;
if(s
<t)
{
temp=R[s];
while(i
<j) while(i!="j)
{
while(j>i && R[j]>=temp) //改成等号
j--;
while(i
<j && r[i]<="temp)
i++;
swap(R[i],R[j]); //交换,你是想交换吧，虽然可以通过异或交换，但难以理解.
}
R[s]=R[i]; //增加的，交换中间数和第一个数
R[i]=temp;
quicksort(R,s,i-1);
quicksort(R,i+1,t);
}
}
int main()
{
int i;
int a[]={5,3,2,1,9,8,7,4,5};
int n = sizeof(a)/sizeof(int);
quicksort(a,0,n-1);
for(i=0;i
<n;i++)
printf("%d ",*(a+i));
// system("pause");
return 1;
}
R[j]^=R[i];
R[i]^=R[j];
R[j]^=R[i];
就是交换R[i]和R[j]
其实，最想说明的是那段交换的代码
R[j]^=R[i];
R[i]^=R[j];
R[j]^=R[i];
一定要排除 i==j 的情况。即自己与自己交换的情况。
如：
a=9;
a^=a;/*a=0*/
a^=a;/*a=0*/
a^=a;/*a=0*/
a就不再是10了。
#include
#include
void quicksort(int R[],int s,int t)
{
int i,j;
int temp;
if(s
<t)
{
temp=R[s];/*选第一个数作为参照*/
/*while(i!=j)不要用这种方法判定循环结束，万一i==j-1，i++，j--后 i〉j了，！=这个条件就救不了你了*/
for(i=s+1,j=t;i<=j;i++,j--)/*不包括参照数，进行左右阵营站队*/
{
while(j>i && R[j]>=temp)/*R[j]>=temp不要 = 也行，加了更好，毕竟相等的无论站左站右，哪边都无所谓*/
j--;
while(i
<j && r[i]<="temp)
i++;
if(i!=j){/*i千万不能等于j*/
R[j]^=R[i];
R[i]^=R[j];
R[j]^=R[i];
}
}
i--;
if(R[s]
<r[i])i--; *调整i的值，使i指向最后一个小于等于参照数的位置*
/*将参照数 与 最后一个小于等于参照数的数进行交换，这样就真正把左右两个阵营分开了*/
R[s]=R[i];
R[i]=temp;
quicksort(R,s,i-1);
quicksort(R,i+1,t);
}
}
int main(void)
{
int i;
int a[]={5,3,2,1,9,8,7,4,5};
quicksort(a,0,sizeof(a)/sizeof(int)-1);
for(i=0;i
<sizeof(a) sizeof(int);i++)
printf("%d ",*(a+i));
return 0;
}
</t)
</n;i++)
</t)
</j&&r[i]
</j)
c语言怎样实现快速排序
include
int arr_num[];
int length;
void quick_sort(int left, int right)
{
int i, j, c, temp;
if(left>right)
return;
i= left;
j= right;
temp = arr_num[i]
while(i != j)
{
while(arr_num[j]>=temp && i
<j)
{
j--;
}
while(arr_num[i]<=temp && i
<j)
{
i++;
}
if(i
<j)
{
c = arr_num[i];
arr_num[i] = arr_num[j];
arr_num[j] = c;
}
}
//left为起始值（参照值）此时的I为第一次排序结束的最后值，与参照值交换位置
arr_num[left] = arr_num[i];
arr_num[i] = temp;
//继续递归直到排序完成
quick_sort(left, i-1);
quick_sort(i+1, right);
}
int main()
{
int i;
length = 7;
arr_num[length] = {23, 7, 17, 36, 3, 61, 49}
//快速排序调用
quick_sort(0, length-1);
//输出排序后的结果
for(i=1;i<=length;i++)
printf("%d ",arr_num[i]);
getchar();getchar();
return 0;
}
</j)
</j)
</j)
快速排序算法c语言
排序算法是《数据结构与算法》中最基本的算法之一。
排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括：
点击以下图片查看大图：
关于时间复杂度 平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；
O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序
线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。
关于稳定性
稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。
不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。
名词解释：
n：数据规模 k："桶"的个数 In-place：占用常数内存，不占用额外内存 Out-place：占用额外内存 稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同 包含以下内容：
1、冒泡排序 2、选择排序 3、插入排序 4、希尔排序 5、归并排序 6、快速排序 7、堆排序 8、计数排序 9、桶排序 10、基数排序 排序算法包含的相关内容具体如下：
冒泡排序算法
冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。
选择排序算法
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n?) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。
插入排序算法
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
希尔排序算法
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
归并排序算法
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
快速排序算法
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
堆排序算法
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。
计数排序算法
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
桶排序算法
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
基数排序算法
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
C语言的快速排序的算法是什么啊？
就是一种算法， 算法的时间复杂度为 nlgn。 是一种排序速度很快的算法， 同时也是不稳定排序算法！
你说的可能是除了冒泡法的方法吧应该是这样的 Array.Sort（数组名）// 把数组升序 Array.Reverse（数组名） //把数组的顺序颠倒 还望采纳
快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 算法过程 设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。 一趟快速排序的算法是： 1）设置两个变量I、J，排序开始的时候：I=0，J=N-1； 2）以第一个数组元素作为关键数据，赋值给key，即 key=A[0]； 3）从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于key的值A[J]，并与key交换； 4）从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于key的A[I]，与key交换； 5）重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后另循环结束。) 例如：待排序的数组A的值分别是：（初始关键数据：X=49） 注意关键X永远不变，永远是和X进行比较，无论在什么位子，最后的目的就是把X放在中间，小的放前面大的放后面。 A[0] A[1] A[2] A[3] A[4] A[5] A[6]： 49 38 65 97 76 13 27 进行第一次交换后：27 38 65 97 76 13 49 ( 按照算法的第三步从后面开始找) 进行第二次交换后：27 38 49 97 76 13 65 ( 按照算法的第四步从前面开始找>X的值，65>49,两者交换，此时：I=3 ) 进行第三次交换后：27 38 13 97 76 49 65 ( 按照算法的第五步将又一次执行算法的第三步从后开始找 进行第四次交换后：27 38 13 49 76 97 65 ( 按照算法的第四步从前面开始找大于X的值，97>49,两者交换，此时：I=4,J=6 ) 此时再执行第三步的时候就发现I=J，从而结束一趟快速排序，那么经过一趟快速排序之后的结果是：27 38 13 49 76 97 65，即所有大于49的数全部在49的后面，所有小于49的数全部在49的前面。 快速排序就是递归调用此过程——在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示： 初始状态 {49 38 65 97 76 13 27} 进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65} 分别对前后两部分进行快速排序 {27 38 13} 经第三步和第四步交换后变成 {13 27 38} 完成排序。 {76 97 65} 经第三步和第四步交换后变成 {65 76 97} 完成排序。
C语言，快速排序算法
0和N-1表示的是数组下标。快排每一趟排序的目的是使值比设定的key值小的数都排到数组前部分，大的都排到后部分；然后对这两部分用新的关键值key分别重复上一步的操作；递归，直到数组有序。其中关键值key=a[low]。用题目给定的数组模拟第一趟排序如下：下标 0 1 2 3 4 5 6 7 8 9值 9 16 47 82 4 66 12 3 25 51low=0 high=9part_element=a[low]=9进入for循环进入第一个whilepart_element<51，于是high--,high=8;part_element<25，high--,high=7;part_element>3,不满足，结束whilea[low]=a[0]=a[high]=a[7]=3,low++,low=1;进入第二个whilepart_element<16,不满足，结束whilea[high]=a[7]=a[low]=a[1]=16,high--,high=6for第一个循环结束，数组如下3 16 47 82 4 66 12 16 25 51low=1,high=6for第二个循环同上，结束时数组如下3 4 47 82 47 66 12 16 25 51low=2,high=3for第三个循环，第一个while中high--以后，low==high，直接break跳出for循环，此时3 4 47 82 47 66 12 16 25 51low=2,high=2结束for以后a[high]=a[2]=part_element=9,得到3 4 9 82 47 66 12 16 25 51split函数return high=2quicksort函数中middle=2;下面两句递归，仍然是调用split函数，对数组0-2,3-9两部分分别重复上述操作最后直到数组数据有序
你好！首先 0 ，n-1 。应该是 数组的坐标（因为n个数字。所以数组的坐标是0 到n-1）而a是你传入的数组。所以他会根据数组的坐标到数组中找到元素。比较并进行排序。递归这段理解如下：首先要了解快速排序的思想：1）随意找一个基准数 。将比基准小的都放到它左边。比它大的都放到它右边。所以当返回基准的坐标的时候。其实这个坐标左边都是小于它的，右边都是大于等于它的。（这里主要是看代码的实现。图中代码是大于等于在右边。也可以自己写小于等于在左边。这个不影响最后结果）2）那么第二次对于返回基准坐标的左右两边。我们同样利用返回的基准坐标找到两个“基准”（如下图）。就会使得返回的这两个基准左右两边有序第三次 用返回的两个基准找到四个基准（如图）然后不断递归..不断的在整体有序的情况下使局部变的有序。假设 为 532348789第一次以a【0】 5为基准 。则：
图中红色标识为基准元素 最后会使得数组全局有序。希望能对你有所帮助。
c语言排序的方法
排序主要分为以下几种。
1.冒泡排序:通过循环比较前后数的大小进行交换。最后使得数组有序。
2.快速排序:首先将第一个数作为一个基准，然后循环，将前半部分大于该数的与后半部分小于该数的进行交换，使得以该数为分界线，前面的小于该数，后面的大于该数，然后分前后两部分继续。
C语言快速排序
*/快速排序算法/*
int Partition(int D[], int l, int r)
{ D[0]=D[l];
while (l
<r) { while (l<r && d[0]<d[r]) r--;
D[l]=D[r];
while (l
=D[l]) l++;
D[r]=D[l]; }
D[r]=D[0];
return r;
}
void Qsort(int D[], int l, int r)
{ int p;
if (l
<r) { p="Partition(D," l, r);
Qsort(D, l, p-1);
Qsort(D, p+1, r); }
}
void QuickSort(int D[], int L)
{ Qsort(D, 1, L);
}
main()
{ int i;
int D[21]={0,12,5,36,13,22,19,2,7,33,52,23,42,25,31,12,20,8,16,27,2};
QuickSort(D,20);
printf("\n");
for(i=1; i<=20; i++) printf("%3d",D[i]);
}
C语言大牛推荐七大排序算法学生来看
C语言7种排序算法附代码
1.冒泡排序
比较相邻的元素。如果第一个比第二个大，就交换它们两个对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数:针对所有的元素重复以上的步骤，除了最后一个;重复步骤1~3，直到排序完成。
2.选择排序
在未排席序列中找到最小(大)元素，存放到排序序列的起始位置从剩余未排序元素中继续寻找最小(大)元素，然后放到已排序序列的末,以此类推，直到所有元素均排序完毕
3.插入排序
从第一个元素开始，该元素可以认为已经被排序;
取出下一个元素，在已经排序的元素序列中从后向前扫描:如果该元素(已排序)大于新元素，将该元素移到下一位置;
4.快速排序
快速排序的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
5.希尔排序
选择一个增量序列t1,t2,"”,tk，其中ti>tj,tk=1;按增量席列个数k，对序列进行k 趟排序;
6.桶排序
设置一个定量的数组当作空桶子
寻访序列，并且把项目一个一个放到对应的桶子去。
对每个不是空的桶子进行排序。
7.基数排序
取得数组中的最大数，并取得位数:
arr为原始数组，从最低位开始取每个位组成radix数组;对radix进行计数排序(利用计数排序适用于小范围数的特点)从不是空的桶子里把项目再放回原来的序列中