一.排序算法
1.插入排序
1) 直接插入排序:(插入类)
1 void InsertSort( ElemType R[], int n )
2 {
3 for ( int i = 2; i <= n; i++ )
4 {
5 if ( R[i].key < R[i - 1].key )
6 {
7 R[0] = R[i];
8 for ( int j = i - 1; j > 0 && ( R[0].key < R[j].key ); j-- )
9 R[j + 1] = R[j];
10 R[j + 1] = R[0];
11 }
12 }
13 }最好情况(顺序有序):
1)比较次数: $sum_{i=2}^{n} 1=n-1$
2)移动次数: 0
最坏情况(逆序有序):
1)比较次数: $sum_{i=2}^{n} i=frac {(n+2)(n-1)}{2}$
2)移动次数: $sum_{i=2}^{n} (i+1)=frac {(n+4)(n-1)}{2}$
2)折半插入排序:(插入类)
1 void BiInsertSort( ElemType R[], int n )
2 {
3 for ( int i = 2; i <= n; i++ )
4 {
5 R[0] = R[i];
6 int low = 1, high = i - 1;
7 while ( low <= high )
8 {
9 int mid = ( low + high ) / 2;
10 if ( R[0].key < R[m].key ) high = mid - 1;
11 else low = mid + 1;
12 }
13 for ( int j = i - 1; j > high; j-- )
14 R[j + 1] = R[j];
15 R[j + 1] = R[0];
16 }
17 }3)希尔排序(又称缩小增量排序)(插入类)
1 // 当dk=1时,即为直接插入排序
2 void ShellSort( ElemType R[], int n )
3 {
4 for ( int dk = n / 2; dk >= 1; dk /= 2 )
5 {
6 for ( int i = dk + 1; i <= n; i++ )
7 {
8 if ( R[i].key < R[i - dk].key )
9 {
10 R[0] = R[i];
11 for ( j = i - dk; j > 0 && ( R[0].key < R[j].key ); j -= dk )
12 R[j + dk] = R[j];
13 R[j + dk] = R[0];
14 }
15 }
16 }
17 }2.交换排序
1)起泡排序(冒泡排序)(交换类)
1 void BubbleSort( ElemType R[], int n )
2 {
3 for ( int i = 1; i <= n - 1; i++ )
4 {
5 bool flag = false;
6 for ( int j = n; j > i; j-- )
7 {
8 if (R[j].key < R[j-1].key )
9 {
10 swap( R[j], R[j - 1] );
11 flag = true;
12 }
13 }
14 if ( !flag ) return;
15 }
16 }2)快速排序:(交换类)
1 void Partition( ElemType R[], int low, int high );
2
3 // 快排
4 void QuickSort( ElemType R[], int low, int high )
5 {
6 if ( low >= high ) return;
7 int pivotpos = Partition( R, low, high );
8 QuickSort( R, low, pivotpos - 1 );
9 QuickSort( R, pivotpos + 1, high );
10 }
11
12 // 划分
13 void Partition( ElemType R[], int low, int high )
14 {
15 ElemType pivot = R[low];
16 while ( low < high )
17 {
18 while ( low < high && R[high].key >= pivot.key ) high--;
19 R[low] = R[high];
20 while ( low < high && R[low].key <= pivot.key ) low++;
21 R[high] = R[low];
22 }
23 R[low] = pivot;
24 return low;
25 }3.选择排序
1)简单选择排序(选择类)
1 void SelectSort( ElemType R[], int n )
2 {
3 for ( int i = 0; i < n - 1; i++ )
4 {
5 int min = i;
6 for ( int j = i + 1; j < n; j++ )
7 {
8 if ( R[j].key < R[min].key ) min = j;
9 }
10 if ( min != i ) swap( R[i], R[min] );
11 }
12 }2)堆排序(选择类)
1 void AdjustDown( ElemType R[], int s, int n );
2
3 void HeapSort( ElemType R[], int n )
4 {
5 for ( int i = n / 2; i > 0; i-- )
6 void AdjustDown( R, i, n );
7 for ( int i = n; i > 1; i-- )
8 {
9 swap( R[i], R[1] );
10 AdjustDown( R, 1, i - 1 );
11 }
12 }
13
14 // 向下调整
15 void AdjustDown( ElemType R[], int s, int n )
16 {
17 R[0] = R[s];
18 for ( int i = 2 * s; i <= n; i *= 2 )
19 {
20 if ( i < n&&R[i].key < R[i + 1].key ) i++;
21 if (R[0].key >=R[i].key ) break;
22 else
23 {
24 R[s] = R[i]; s = i;
25 }
26 }
27 R[s] = R[0];
28 }
29
30 // 向上调整
31 void AdjustUp( ElemType R[], int s )
32 {
33 R[0] = R[s];
34 int p = s / 2;
35 while ( p > 0 && R[p].key < R[0].key )
36 {
37 R[s] = R[p];
38 s = p;
39 p /= 2;
40 }
41 R[s] = R[0];
42 }4.归并排序(归并类)
1 void Merge( ElemType R[], int low, int mid, int high );
2
3 void MergeSort( ElemType R[], int low, int high )
4 {
5 if ( low >= high ) return;
6 int mid = ( low + high ) / 2;
7 MergeSort( R, low, mid );
8 MergeSort( R, mid + 1, high );
9 Merge( R, low, mid, high );
10 }
11
12 ElemType B[MAXSIZE];
13 void Merge( ElemType R[], int low, int mid, int high )
14 {
15 int i,j,k;
16 for ( i = low; i <= high; i++ )
17 B[i] = R[i];
18 i = k = low, j = mid + 1;
19 while ( i <= mid && j <= high )
20 {
21 if ( B[i].key <= B[j].key )
22 R[k++] = B[i++];
23 else
24 R[k++] = B[j++];
25 }
26 while ( i <= mid ) R[k++] = B[i++];
27 while ( j <= high ) R[k++] = B[j++];
28 }二.综合题(算法)
1.设顺序表用数组R[]表示,表中存储在数组下标1~m+n的范围内,前m个元素递增有序,后n个元素递增有序,设计一个算法,使得整个顺序表有序
1 void InsertSort( ElemType R[], int m, int n )
2 {
3 for ( int i = m + 1; i <= m + n; i++ )
4 {
5 if ( R[i].key < R[i - 1].key )
6 {
7 R[0] = R[i];
8 for ( int j = i - 1; j > 0 && ( R[0].key < R[j].key ); j-- )
9 R[j + 1] = R[j];
10 R[j + 1] = R[0];
11 }
12 }
13 }2.计数排序:对表进行排序并将结果放到另一个新的表中,要求表中所有关键码互不相同
1 void CountSort( ElemType A[], ElemType B[], int n )
2 {
3 for ( int i = 0; i < n; i++ )
4 {
5 int cnt = 0;
6 for ( int j = 0; j < n; j++ )
7 if ( A[i].key > A[j].key )cnt++;
8 B[cnt] = A[i];
9 }
10 }3.双向冒泡排序
1 // 思想:第一趟通过交换把最大的放最后,第二趟通过交换把最小的放最前,反复进行
2 void BubbleSort( ElemType A[], int n )
3 {
4 int low = 0, high = n - 1, i;
5 bool flag = true;
6 while ( low < high && flag )
7 {
8 flag = false;
9 for (i = low; i < high; i++ )
10 {
11 if (A[i]>A[i+1] )
12 {
13 swap( A[i], A[i + 1] ); flag = true;
14 }
15 }
16 high--;
17 for ( i = high; i > low; i-- )
18 {
19 if ( A[i] < A[i - 1] )
20 {
21 swap( A[i], A[i - 1] ); flag = true;
22 }
23 }
24 low++;
25 }
26 }4.单链表的简单选择排序(假设不带表头结点)
1 void SelectSort( LinkList& L )
2 {
3 LinkList h, p, s, pre, r;
4 h = L;
5 while ( h )
6 {
7 p = s = h; pre = r = NULL;
8 // 找最大结点s
9 while ( p )
10 {
11 if (p->data>s->data )
12 {
13 s = p; r = pre;
14 }
15 pre = p;
16 p = p->next;
17 }
18 // 脱链
19 if ( s == h ) h = h->next;
20 else r->next = s->next;
21 // 头插法
22 s->next = L; L = s;
23 }
24 }5.顺序表中有n个不同整数(下标1~n),设计算法把所有奇数移动到偶数前面(时,空都最少)
1 void Move( ElemType A[], int n )
2 {
3 int low = 1, high = n;
4 while ( low < high )
5 {
6 while ( low < high&&A[low] % 2 ) low++;
7 while ( low < high && A[high] % 2 == 0 ) high--;
8 if ( low < high )
9 {
10 swap( A[low], A[high] );
11 low++; high--;
12 }
13 }
14 }6.在顺序表中找出第k小的元素(时空最少)
1 // 思想:划分
2 int Partition( ElemType R[], int low, int high )
3 {
4 int pivot = R[low];
5 while ( low < high )
6 {
7 while ( low < high && R[high].key >= pivot.key ) high--;
8 R[low] = R[high];
9 while ( low < high&& R[low].key <= pivot.key ) low++;
10 R[high] = R[low];
11 }
12 R[low] = pivot;
13 return low;
14 }
15
16 ElemType Kth_elem( ElemType R[], int low, int high, int k )
17 {
18 int pivotpos = Partition( R, low, high );
19 if ( pivotpos == k ) return R[pivotpos];
20 else if ( pivotpos > k ) return Kth_elem( R, low, pivotpos - 1, k );
21 else return Kth_elem( R, pivotpos + 1, high, k );
22 }7.n个正整数构成的集合A,将其划分为两个不相交的子集$A1,A2$,元素个数分别是n1和n2.A1和A2中元素之和分别为S1和S2.设计一个时空高效算法,使|n1-n2|最小且|s1-s1|最大.(下标从1开始)
1 int Partition( ElemType R[], int low, int high )
2 {
3 int pivot = R[low];
4 while ( low < high )
5 {
6 while ( low < high && R[high].key >= pivot.key ) high--;
7 R[low] = R[high];
8 while ( low < high&& R[low].key <= pivot.key ) low++;
9 R[high] = R[low];
10 }
11 R[low] = pivot;
12 return low;
13 }
14
15 int SetPartition( ElemType R[], int n, int low, int high )
16 {
17 int k = n / 2, s1, s2, i;
18 int pivotpos = Partition( R, low, high );
19 if ( pivotpos == k )
20 {
21 s1 = s2 = 0;
22 for ( i = 1; i <= k; i++ ) s1 += R[i];
23 for ( j = k + 1; j <= n; j++ ) s2 += R[j];
24 return s2 - s1;
25 }
26 else if ( pivotpos > k )
27 return SetPartition( R, n, low, pivotpos - 1 );
28 else return SetPartition( R, n, pivotpos + 1, high );
29 }