高级守护
有没有人能和我解释一下快速排序的思想？
初级守护
思想如下：
快速排序基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：
1）、设置两个变量I、J，排序开始的时候I：=1，J：=N；
2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；
3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；
4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；
5）、重复第3、4步，直到I=J；
例如：待排序的数组A的值分别是：（初始关键数据X：=49）
A[1] A[2] A[3] A[4] A[5] A[6] A[7]：
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,两者交换，此时J：=4 )
此时再执行第三步的时候就发现I=J，从而结束一躺快速排序，那么经过一躺快速排序之后的结果是：27 38 13 49 76 97 65，即所以大于49的数全部在49的后面，所以小于49的数全部在49的前面。
快速排序就是递归调用此过程--再以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列。
1）、设有N（假设N=10）个数，存放在S数组中；
2）、在S[1。。N]中任取一个元素作为比较基准，例如取T=S[1]，起目的就是在定出T应在排序结果中的位置K，这个K的位置在：S[1。。K-1]<=S[K]<=S[K+1..N]，即在S[K]以前的数都小于S[K]，在S[K]以后的数都大于S[K]；
3）、利用分治思想（即大化小的策略）可进一步对S[1...K-1]和S[K+1...N]两组数据再进行快速排序直到分组对象只有一个数据为止。
如具体数据如下，那么第一躺快速排序的过程是：
45 36 18 53 72 30 48 93 15 36
I J
（1）36 36 18 53 72 30 48 93 15 45
（2）36 36 18 45 72 30 48 93 15 53
（3）36 36 18 15 72 30 48 93 45 53
（4）36 36 18 15 45 30 48 93 72 53
（5）36 36 18 15 30 45 48 93 72 53
通过一躺排序将45放到应该放的位置K，这里K=6，那么再对S[1...5]和S[6...10]分别进行快速排序。
初级守护
分而治之
高级天翼
分而治之
初级启示者
二分思想
初级启示者
分而冶之
新手光能
首先找到a[]的中心，记录为mid，先把第1个拿去与mid比，如果第1个小于mid（这里默认目标让a[]从小到大），则跳到第2个继续与mid比，知道找到大于mid，再从最后一个往前如法炮制，然后看前面找到的那个数的位置有没有到后面找到的那个数的后面，如果没有，则交换这两个数，然后前面的个数的位置往右移，后面那个数的位置往前移，一直重复到前面找到的那个数的位置到后面找到的那个数的后面。这时，则判断两个数有没有超过边界。if(前面的边界<后找到的数的位置) qsort(前面的边界,后找到的数的位置); if(先找到的数的位置<后面的边界)qsort(先找到的数的位置,后面的边界);
修练者
从小到大排序：
sort(a,a+n);
从大到小排序：
bool cmp(int a,int b)
{
return a>b;
}
sort(a,a+n,cmp);
资深守护
qsort()
初级光能
分而治之
资深光能
快速排序是对冒泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
假设待排序的序列为{a[L],a[L+1],a[L+2],……,a[R]}，首先任意选取一个记录（通常可选中间一个记作为枢轴或支点），然后重新排列其余记录，将所有关键字小于它的记录都放在左子序列中，所有关键字大于它的记录都放在右子序列中。由此可以将该“支点”记录所在的位置mid作分界线，将序列分割成两个子序列和。这个过程称作一趟快速排序（或一次划分）。
一趟快速排序的具体做法是：附设两个指针i和j，它们的初值分别为L和R，设枢轴记录取mid，则首先从j所指位置起向前搜索找到第一个关键字小于的mid的记录，然后从i所指位置起向后搜索，找到第一个关键字大于mid的记录，将它们互相交换，重复这两步直至i>j为止。
快速排序的时间的复杂性是O(nlog2n)，速度快,但它是不稳定的排序方法。就平均时间而言，快速排序是目前被认为是最好的一种内部排序方法
由以上讨论可知，从时间上看，快速排序的平均性能优于前面讨论过的各种排序方法，但快速排序需一个栈空间来实现递归。若每一趟排序都将记录序列均匀地分割成长度相接近的两个子序列，则栈的最大深度为log(n+1)。
新手天翼
分而治之，分治思想
高级守护
分而冶之！
新手天翼
我发现一个问题
老帖里怎么全都是禁言的人
新手光能
二分
初级天翼
排序：
1.选择排序
2.冒泡排序
3.快速排序
中级守护
举个例子:
2 3 8 7 1 4 6 9 5
先从数列中任意选取一个数,现在我选取最后一个5
然后把其他数依次与这个数进行比较，如果小于他则放在左边，反之，放右边
于是产生两列新的数
左侧是：2 3 1 4
右侧是：8 7 6 9
合起来是 2 3 1 4 / 5 / 8 7 6 9
容易看出，如果能把左右两侧数列分别排好序，那么整个数列就排好序了。
我们对左右两侧看成两个独立的新数列，重复执行上述步骤。
例如对于左侧，选取2，那么得出 1 / 2 / 3 4。
这时候产生了新的左侧和右侧，如果左侧或右侧个数为0或者为1，那就已经排好序了，不必处理。而右侧的3 4虽然看上去已经排好序了，但是仍需验证。可以对3 4 重复上述步骤。选取4，得出 3 / 4 / 空。
至此，左侧排序完成：
1 2 3 4/ 5/ 8 7 6 9
右侧使用相同方法，不再重复
资深光能
void qsort(int a[],int l,int r)
{
int i,j;
int mid;
i=l;j=r;
mid=a[(l+r)/2];
if(i<=j)
{
while(mid>a[i])i++;
while(a[j]>mid)j--;
while(i<=j)
{
swap(a[i],a[j]);
i++;j--;
}
}
if(i<r)qsort(a,i,r);
if(j>l)qsort(a,l,j);
}
//从小到大
资深天翼
?
修练者
快速排序是对冒泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
假设待排序的序列为{a[L],a[L+1],a[L+2],……,a[R]}，首先任意选取一个记录（通常可选中间一个记作为枢轴或支点），然后重新排列其余记录，将所有关键字小于它的记录都放在左子序列中，所有关键字大于它的记录都放在右子序列中。由此可以将该“支点”记录所在的位置mid作分界线，将序列分割成两个子序列和。这个过程称作一趟快速排序（或一次划分）。
一趟快速排序的具体做法是：附设两个指针i和j，它们的初值分别为L和R，设枢轴记录取mid，则首先从j所指位置起向前搜索找到第一个关键字小于的mid的记录，然后从i所指位置起向后搜索，找到第一个关键字大于mid的记录，将它们互相交换，重复这两步直至i>j为止。
快速排序的时间的复杂性是O(nlog2n)，速度快,但它是不稳定的排序方法。就平均时间而言，快速排序是目前被认为是最好的一种内部排序方法
由以上讨论可知，从时间上看，快速排序的平均性能优于前面讨论过的各种排序方法，但快速排序需一个栈空间来实现递归。若每一趟排序都将记录序列均匀地分割成长度相接近的两个子序列，则栈的最大深度为log(n+1)。
新手守护
快速排序通常有
选择排序和冒泡排序。
1，选择排序
代码为：
int a[5]={8,-1,9,6,-2},n;
cin>>n;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(a[i]<=a[j])
int t=a[i];a[i]=a[j];a[j]=t;
}
}数列变成{9,8,6，-1，-2}
2，冒泡排序
例如，有2,3,5,7,9五个数
现在打乱成5,2,7,9,3
第一轮：
5 2 7 9 3 ---------5大于2，不换
5 2 7 9 3 ---------2小于7，换
5 7 2 9 3 ---------2小于9，换
5 7 9 2 3 ---------2小于3，换
第二轮：
5 7 9 3 2 ---------5小于7，换
7 5 9 3 2 ---------5小于9，换
7 9 5 3 2 ---------5大于3，不换
第三轮：
7 9 5 3 2 ---------7小于9，换
9 7 5 3 2 ---------7大于5，不换
第四轮：
9 7 5 3 2 ---------9大于7，不换
就变成了9，7，5，3，2
其实排到第三轮就够了，第四轮是用来核对的
请老师采纳，谢谢！
