数据结构知识点总结

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]； }