SMART算法总结

）；而对于数据量大的，（

1

< br>）为首要。

主要排序法有：

一、冒泡（

Bubble

）排序——相邻交换

二、选择排序——每次最小

/

大排在相应的位 置

三、插入排序——将下一个插入已排好的序列中

Shell

）排序——缩小增量

五、归并排序

六、快速排序

七、堆排序

八、拓扑排序

九、锦标赛排序

十、基数排序

一、冒泡（

Bubble

）排序

----------------------------------Code

从小到大排序

n

个数

< br>------------------------------------

void BubbleSortArray()

{

for(int i=1;i

{

for(int j=0;i

{ < /p>

if(a[j]>a[j+1])//

比较交换相邻元素

{

int temp;

temp=a[j]; a[j]=a[j+1]; a[j+1]=temp;

}

}

}

}

------------------------- ------------------------Code---------------------- --------------------------

效率

O

（

n

?）

,

适用于排序小列表。

二、选择排序

----------------------------------Code

从小到大排序

n

个数

< br>--------------------------------

void SelectSortArray()

{

int min_index;

for(int i=0;i

{

min_index=i;

for(int j=i+1;j

每次扫描选择最小项

if(arr[j]

if(min_index!=i)//

找到最小项交换，即将 这一项移到列表中的正确位置

{

int temp;

temp=arr[i]; arr[i]=arr[min_index]; arr[min_index]=temp;

}

}

}

< br>----------------------------------------------- --Code----------------------------------------- < /p>

效率

O

（

n

?），适用于排序小的列表。

三、插入排序

< br>--------------------------------------------Cod e

从小到大排序

n

个数

-------------------------------------

void InsertSortArray()

{

for(int i=1;i

循环从第二个 数组元素开始，因为

arr[0]

作为最初已排序部分

{

int temp=arr[i]; //temp

标记为未排序第一个元素

int j=i-1;

while (j>=0 && a rr[j]>temp)/*

将

temp

与已排序元素从小到大比较，寻找

temp

应插入的位置

*/

{

arr[j+1]=arr[j];

j--;

}

arr[j+1]=temp;

}

}

----------- -------------------Code--------------------------- -----------------------------------

最佳 效率

O

（

n

） ；最糟效率

O

（

n

?）与冒泡、选择相同，适用于排序小列表

若列表基本有序，则插入排序比冒泡、选择更有效率。

四、壳（

Shell

）排序——缩小增量排序

-------------------------------------Code

从小到大排序

n

个数

---- ---------------------------------

void ShellSortArray()

{

for(int incr=3;incr<0;incr--)//

增量递减，以增量

< br>3

，

2

，

1

为例

{

for(int L=0;L<(n-1)/incr;L++)//

< br>重复分成的每个子列表

{

for(int i=L+incr;i

< br>对每个子列表应用插入排序

{

int temp=arr[i];

int j=i-incr;

while(j>=0&&arr[j]>temp)

{

arr[j+incr]=arr[j];

j-=incr;

}

arr[j+incr]=temp;

}

}

}

}

< br>--------------------------------------Code----- --------------------------------------

适用于排序小列表。

效率估计

O

（

nlog2^n

）

~O

（

n^1.5

），取决于增量值的最初大小。建议使用质数作为增量值，因为如果增量值是

2

的幂，则在下一个通道中会再次比较相同的

元素。

壳（

Shell

）排序 改进了插入排序，减少了比较的次数。是不稳定的排序，因为排序过程中元素可能会前后跳跃。

< br>

五、归并排序

--------- -------------------------------------Code

< br>从小到大排序

------------------------------ ---------

void MergeSort(int low,int high)

{

if(low>=high) return;//

每个子列表中剩下一个元素时停止

else int mid=(low+high)/2;/*

将列表划分成相等的两个子列表

,

若有奇数个元素，则在左边子 列表大于右侧子列表

*/

MergeSort(low,m id);//

子列表进一步划分

MergeSort(mid+1,high);

int [] B=new int [high- low+1];//

新建一个数组，用于存放归并的元素

for(int i=low,j=mid+1,k=low;i<=mid && j <=high;k++)/*

两个子列表进行排序归并，直到两个子列表中的一个结束< /p>

*/

{

if (arr[i]<=arr[j];)

{

B[k]=arr[i];

I++;

}

else

{ B[k]=arr[j]; j++; }

}

for( ;j<=high;j++,k++)//

如果第二个子列表中仍然有元素，则追加到新 列表

B[k]=arr[j];

for( i<=mid;i++,k++)//

如果在第一 个子列表中仍然有元素，则追加到新列表中

B[k]=arr[i];

for(int z=0;z

将排序的数组

B

的

所有元素复制到原始数组

arr

中

arr[z]=B[z];

}

-------------------------------------------------- ---Code------------------------------------------- --------

效率

O

（

nlogn

），归并的最佳、平均和最糟用例效率之间没有差异。

适用于排序大列表，基于分治法。

六、快速排序

< br>------------------------------------Code------- -------------------------------------

/*

快速排序的算法思想：选定一个枢纽元素，对待排序序列进行分割，分割之后的序列 一个部分小于枢纽元素，一个部分大于枢纽元素，再对这两个分割好的

子序列进行上述的 过程。

*/ void swap(int a,int b){int t;t =a ;a =b b =t }

int Partition(int [] arr,int low,int high)

{

int pivot=arr[low];//

采用子序列的第 一个元素作为枢纽元素

while (low < high)

{

//

从后往前栽 后半部分中寻找第一个小于枢纽元素的元素

while (low < high && arr[high] >= pivot)

{

--high;

}

//

将这个比枢纽元素小的元素交换到前半部分

swap(arr[low], arr[high]);

//

从前往后在前半部分中寻找第一个大于枢纽元素的元素

while (low

{

++low

}

swap (arr [low ],arr [high ]);//

将这个枢纽元素大的元素交换到后半部分

}

return low ;//

返回枢纽元素所在的位置

}

void QuickSort(int [] a,int low,int high)

{

if (low

{

int n=Partition (a ,low ,high );

QuickSort (a ,low ,n );

QuickSort (a ,n +1,high );

}

}

----------- -----------------------------Code----------------- --------------------

平均效率

O< /p>

（

nlogn

），适用于排序大列表。< /p>

此算法的总时间取决于枢纽值的位置；选择第一个元素作为枢 纽，可能导致

O

（

n

< br>?）的最糟用例效率。若数基本有序，效率反而最差。选项中间值作为枢纽，

效率 是

O

（

nlogn

）。

基于分治法。

七、堆排序

最大堆：后者任一非终 端节点的关键字均大于或等于它的左、右孩子的关键字，此时位于堆顶的节点的关键字是整个序列中最大的。

思想：

( 1)

令

i=l,

并令

< br>temp

＝

kl

(2 )

计算

i

的左孩子

j=2i+1;

(3)

若

j<

＝

n

－

1

，则转

(4),

否则转

(6);

(4)

比较

kj

和

kj+1,

若

k j+1>kj,

则令

j

＝

j

＋

1

，否则

j

不变；

(5)

比较

temp

和

kj

，若

kj>temp

，则令