Question

最快的排序方法和题目.

很难啊!!

Answer 1

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

假设要排序的数组是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为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示：

初始状态 {49 38 65 97 76 13 27}

进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65}

分别对前后两部分进行快速排序 {13} 27 {38}

结束 结束 {49 65} 76 {97}

49 {65} 结束

结束

图6 快速排序全过程

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]两组数据再进行快速排序直到分组对象只有一个数据为止。 1 2 3 4 5 6 7 8 9 10

如具体数据如下，那么第一躺快速排序的过程是：

数组下标：

45 36 18 53 72 30 48 93 15 36

5） 36 36 18 15 30 45 48 93 72 534） 36 36 18 15 45 30 48 93 72 533） 36 36 18 15 72 30 48 93 45 532） 36 36 18 45 72 30 48 93 15 53

program kuaisu(input,output);
const n=10;
var
s:array[1..10] of integer;
k,l,m:integer;

procedure qsort(lx,rx:integer);
var
I,j,t:integer;
Begin
I:lx;j:rx;t:s[I];
Repeat
While (s[j]>t) and (j>I) do
Begin
k:=k+1;
j:=j-1
end;
if I<j then
begin
s[I]:=s[j];I:=I+1;l:=l+1;
while (s[I]<t) and (I<j) do
begin
k:=k+1;
I:=I+1
End;
If I<j then
begin
S[j]:=s[I];j:=j-1;l:=l+1;
End;
End;
Until I=j;
S[I]:=t;I:=I+1;j:=j-1;l:=l+1;
If lx<j then qsort(lx,j);
If I<rx then qsort(I,rx)
End;{过程qsort结束}

Begin
Writeln('input 10 integer num:');
For m:=1 to n do read(s[m]);
K:=0;l:=0;
Qsort(l,n);
Writeln('排序后结果是：')；
For m:=1 to n do write(s[m]:4)
End.

通过一躺排序将45放到应该放的位置K，这里K=6，那么再对S[1。。5]和S[6。。10]分别进行快速排序。程序代码如下：<49,两者交换，此时J:=6>

Answer 2

所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。其确切定义如下：
输入：n个记录R1，R2，…，Rn，其相应的关键字分别为K1，K2，…，Kn。
输出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。

这里，我们简单介绍几种排序方法，直接插入排序、希儿排序、冒泡排序、快速排序、直接选择排序，文中所提及的代码在IE6下测试通过。

直接插入排序基本思想
假设待排序的记录存放在数组R[1..n]中。初始时，R[1]自成1个有序区，无序区为R[2..n]。从i=2起直至i=n为止，依次将R[i]插入当前的有序区R[1..i-1]中，生成含n个记录的有序区。

算法描述
function InsertSort(arr) { //插入排序->直接插入法排序
var st = new Date();
var temp, j;
for(var i=1; i<arr.length; i++) {
if((arr[i]) < (arr[i-1])) {
temp = arr[i];
j = i-1;
do {
arr[j+1] = arr[j];
j--;
}
while (j>-1 && (temp) < (arr[j]));
arr[j+1] = temp;
}//endif
}
status = (new Date() - st) + ' ms';
return arr;
}

希尔排序基本思想
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。

算法描述

function ShellSort(arr) { //插入排序->希儿排序
var st = new Date();
var increment = arr.length;
do {
increment = (increment/3|0) + 1;
arr = ShellPass(arr, increment);
}
while (increment > 1)

status = (new Date() - st) + ' ms';
return arr;
}
function ShellPass(arr, d) { //希儿排序分段执行函数
var temp, j;
for(var i=d; i<arr.length; i++) {
if((arr[i]) < (arr[i-d])) {
temp = arr[i]; j = i-d;
do {
arr[j+d] = arr[j];
j = j-d;
}
while (j>-1 && (temp) < (arr[j]));
arr[j+d] = temp;
}//endif
}
return arr;
}

冒泡排序基本思想
将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。

算法描述
function BubbleSort(arr) { //交换排序->冒泡排序
var st = new Date();
var temp;
var exchange;
for(var i=0; i<arr.length; i++) {
exchange = false;
for(var j=arr.length-2; j>=i; j--) {
if((arr[j+1]) < (arr[j])) {
temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
exchange = true;
}
}
if(!exchange) break;
}
status = (new Date() - st) + ' ms';
return arr;
}

快速排序基本思想
将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
在R[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。

算法描述
function QuickSort(arr) { //交换排序->快速排序
if (arguments.length>1) {
var low = arguments[1];
var high = arguments[2];
} else {
var low = 0;
var high = arr.length-1;
}
if(low < high){
// function Partition
var i = low;
var j = high;
var pivot = arr[i];
while(i<j) {
while(i<j && arr[j]>=pivot)
j--;
if(i<j)
arr[i++] = arr[j];
while(i<j && arr[i]<=pivot)
i++;
if(i<j)
arr[j--] = arr[i];
}//endwhile
arr[i] = pivot;
// end function
var pivotpos = i; //Partition(arr，low，high);
QuickSort(arr, low, pivotpos-1);
QuickSort(arr, pivotpos+1, high);
} else
return;
return arr;
}

直接选择排序基本思想
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：
①初始状态：无序区为R[1..n]，有序区为空。
②第1趟排序
在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
……
③第i趟排序
第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[i]交换，使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。

算法描述
function SelectSort(arr) { //选择排序->直接选择排序
var st = new Date();
var temp;
for(var i=0; i<arr.length; i++) {
var k = i;
for(var j=i+1; j<arr.length; j++) {
if((arr[j]) < (arr[k]))
k = j;
}
if (k != i){
temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
status = (new Date() - st) + ' ms';
return arr;
}

从运行速度上来看，快速排序是最快的。