数据结构知识点总结 下载本文

void SelectSort(int r[], int n) {

for ( i ? 1; i ≤ n-1; i++ )

for ( j ? i+1; j ≤ n; j++ ) if ( r[j] < r[k] )

r[i] ?? r[k];

}

简单选择排序优化后的算法。

void SelectSort(int r[], int n) {

for ( i ? 1; i ≤ n-1; i++ ) {

k ? i;

for ( j ? i+1; j ≤ n; j++ ) if ( r[j] < r[k] ) k ? j; if ( k ≠ i )

r[i] ?? r[k];

} }

下面是冒泡排序算法,效率不高

void BubbleSort (int r[], int n) {

for ( i = 1; i < n; i++ )

for (j = 1; j ≤ n-1; j++ ) if ( r[j] > r[j+1] )

r[j] ?? r[j+1]; }

冒泡排序优化后的算法。

void BubbleSort (int r[], int n) {

exchange ? TRUE; k ? n – 1;

while ( exchange ) {

exchange ? FALSE;

for (i = 1; i ≤ k; i++ ) if ( r[i] > r[i+1] ) {

r[i] ?? r[i+1]; exchange ? TRUE; } k ? k – 1;

} }

设有两个有序关键字表S1,S2。S1和S2存储在数组r[low,high]中,Sl放在r

[low,mid]中,S2放在r[mid+1,high]中,如下图所示。现在要把S1,S2归并,请写出归并排序算法。算法头部约定为:void Merge(r[],

low, mid, high) low mid mid+1

high

算法如下:

void Merge(r[], low, m, high) {

k ? 1; i ? low; j ? m + 1;

while ( i ≤ m && j ≤ high ) {

if ( r[i].key ≤ r[j].key ) {

r’[k] ? r[i]; i ? i + 1; } else {

r’[k] ? r[j]; j ? j + 1; }

k ? k + 1; }

while ( j ≤ h ) {

r’[k] ? r[j]; j ? j + 1; k ? k + 1; }

while ( i ≤ m ) {

r’[k] ? r[i]; i ? i + 1; k ? k + 1; }

for (p=1,i=low; i≤high; p++,i++) r[i] ? r’[p]; }