快速排序方法

A. 快速排序算法和西尔排序

快速排序（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]，并与A[I]交换；
4）从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于key的A[I]，与A[J]交换；
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语言快速排序法:
#include<stdio.h>
void run(int *pData,int left,int right)
{
int i,j;
int middle,iTemp;
i=left;
j=right;
middle=pData[(left+right)/2];//求中间值
do
{
while((pData[i]<middle)&&(i<right))//从左扫描大于中值的数
i++;
while((pData[j]>middle)&&(j>left))//从右扫描大于中值的数
j--;
if(i<=j)//找到了一对值
{//交换
iTemp=pData[i];
pData[i]=pData[j];
pData[j]=iTemp;
i++;
j--;
}
}
while(i<=j);//如果两边扫描的下标交错，就停止（完成一次）
if(left<j)//当左边部分有值(left＜j)，递归左半边
run(pData,left,j);
if(right>i)//当右边部分有值(right＞i)，递归右半边
run(pData,i,right);
}

void QuickSort(int *pData,int Count)
{
run(pData,0,Count-1);
}
void main()
{
int data[10];
for(int i=9,j=0;i>=0;i--,j++)
data[j]=i;
QuickSort(data,10);
for(int k=0;k<10;k++)
cout<<data[k]<<" ";
cout<<"\n";
}

直接来分析算法：首先我们考虑最理想的情况
1.数组的大小是2的幂，这样分下去始终可以被2整除。假设为2的k次方，即k＝log2(n)。
2.每次我们选择的值刚好是中间值，这样，数组才可以被等分。
第一层递归，循环n次，第二层循环2＊(n/2)......
所以共有n+2(n/2)+4(n/4)+...+n＊(n/n) ＝ n+n+n+...+n＝k＊n＝log2(n)＊n
所以算法复杂度为O(log2(n)＊n)
==========================================================================

希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。
希尔排序基本思想：
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。 该方法实质上是一种分组插入方法。
给定实例的shell排序的排序过程
假设待排序文件有10个记录，其关键字分别是：
49，38，65，97，76，13，27，49，55，04。
增量序列的取值依次为： 5，3，1
希尔排序(缩小增量法) 属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序 排序过程：先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止
初始：d＝5
49 38 65 97 76 13 27 49* 55 04
49 13
|-------------------|
38 27
|-------------------|
65 49*
|-------------------|
97 55
|-------------------|
76 04
|-------------------|
一趟结果
13 27 49* 55 04 49 38 65 97 76
d=3
13 27 49* 55 04 49 38 65 97 76
13 55 38 76
|------------|------------|------------|
27 04 65
|------------|------------|
49* 49 97
|------------|------------|
二趟结果
13 04 49* 38 27 49 55 65 97 76
d=1
13 04 49* 38 27 49 55 65 97 76
|----|----|----|----|----|----|----|----|----|
三趟结果
04 13 27 38 49* 49 55 65 76 97
--------------------------------------------------------------------------------------------
算法思想简单描述： 在直接插入排序算法中，每次插入一个数，使有序序列只增加1个节点， 并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离（称为 增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除 多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现 了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中 记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量 对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成 一组，排序完成。 下面的函数是一个希尔排序算法的一个实现，初次取序列的一半为增量， 以后每次减半，直到增量为1。 希尔排序是不稳定的。

希尔排序的C#实现
using System;
public class ShellSorter
{
public void Sort(int[] list)
{
int inc;
for (inc = 1; inc <= list.Length / 9; inc = 3 * inc + 1) ;
for (; inc > 0; inc /= 3)
{
for (int i = inc + 1; i <= list.Length; i += inc)
{
int t = list[i - 1];
int j = i;
while ((j > inc) && (list[j - inc - 1] > t))
{
list[j - 1] = list[j - inc - 1];
j -= inc;
}
list[j - 1] = t;
}
}
}
}
public class MainClass
{
public static void Main()
{
int[] iArrary = new int[] { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 };
ShellSorter sh = new ShellSorter();
sh.Sort(iArrary);
for (int m = 0; m <= 13; m++)
Console.WriteLine("{0}", iArrary[m]);
Console.ReadKey();
}
}

B. 快速排序算法有什么作用

首先它是一种排序算法，排序算法是为了让无序的数据组合变成有序的数据组合。

有序的数据组合最大的优势是在于当你进行数据定位和采用时，
会非常方便，因为这个数据是有序的
从而在代码设计的时候会让你避免很多不必要的麻烦，
因为无序数据你在进行推断数据前后关系的时候会显示很繁琐

快速排序是排序中的一种，它在最差情况下和别的排序相差不大
而在最优，一般情况下，会比一般的排序方法更节省时间

这里的一般排序是指：起泡，希尔，插入等常规排序方法

其实我个人更喜欢插入，不过这对于链表操作更方便，因为容易操作……

C. 求问关于快速排序算法

当然变了啊 你说的i是快排的区间起始节点吧

D. 写出快速排序的算法

快速排序算法通过多次比较和交换来实现排序，其排序算法如下：
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

E. C++快速排序算法

int qpass(RecordYype r[],int left,int right)/*对记录数组r中的r[left]至r[right]部分进行一趟排序，并得到枢轴的位置，使得排序后的结果满足期之后（前）的记录的关键字均不小于（大于）枢轴记录*/
{
x=r[left];
low=left; high=right;
while(low<high)
{
while(low<high&&r[high].key>=x.key) /*high从右向左找小于x.key的记录*/
high--;
if(low<high) {r[low]=r[high]; low++;} /*找到小于x.key的记录，则进行交换*/
while(low<high&&r[left].key<=x.key ) /*low从左到右找大于x.key的记录*/
if(low<high) {r[high]=r[low]; high--;} /*找到大于x.key的记录，则进行交换*/
}
r[low]=x; /*将枢轴记录保存到low=high的位置*/
return low; /*返回枢轴记录的位置*/
}

F. 快速排序法，

66 13 51 76 81 26 57 69 23
23 13 51 76 81 26 57 69 66
23 13 51 66 81 26 57 69 76
23 13 51 57 81 26 66 69 76
23 13 51 57 66 26 81 69 76
23 13 51 57 26 66 81 69 76

第一次排序过程如上
void sort(int *a,int l,int r)
{
int k=a[l],i=l,j=r;
while (i<j)
{
while (i<j)
{
if (a[j]<k) {swap(a[i],a[j]);print(a,n); break;}
j--;
}
while (i<j)
{
if (a[i]>k) {swap(a[i],a[j]);print(a,n); break;}
i++;
}
}

if (i-l>=1) sort(a,l,i);
if (r-i-1>=1) sort(a,i+1,r);

｝

G. 关于快速排序算法

当待排序区间中的关键码都相同，也就是快速排序的最坏情况，其运行时间是
O(n^2)，然而但在关键码不全相同时，如果总是选择中项作为主元，它的时间复杂性是O(nlogn)。
尽管在最坏情况下，快排表现出的运行时间为O（n^2），但它的平均时间复杂度仍是O(nlogn)。

H. 快速排序算法原理与实现

快速排序的原理：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小。

然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

假设要排序的数组是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。

(8)快速排序方法扩展阅读：

设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。

值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。

一趟快速排序的算法是：

1、设置两个变量i、j，排序开始的时候：i=0，j=N-1；

2、以第一个数组元素作为关键数据，赋值给key，即key=A[0]；

3、从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]的值赋给A[i]；

4、从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]的值赋给A[j]；

5、重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。