数据结构第16周 ：（ 希尔排序+ 堆排序 + 快速排序 ）

希尔排序

【问题描述】给出一组数据，请用希尔排序将其按照从小到大的顺序排列好。

【输入形式】原始数据，以0作为输入的结束；第二行是增量的值，都只有3个。

【输出形式】每一趟增量排序后的结果

【样例输入】

8 3 6 1 68 12 19 3 1 0

5 3 1

【样例输出】

8 3 3 1 68 12 19 6 1
1 3 1 8 6 3 19 68 12
1 1 3 3 6 8 12 19 68

【样例输入】

5 3 9 8 2 4 1 7 10 6 0

4 2 1

【样例输出】

2 3 1 7 5 4 9 8 10 6
1 3 2 4 5 6 9 7 10 8
1 2 3 4 5 6 7 8 9 10

#include<iostream>
using namespace std;void ShellSort(int a[], int ick, int limit)
{int i, j;for(i = ick; i < limit; i ++){int temp = a[i];for(j = i - ick; j >= 0 && temp < a[j]; j -= ick){a[j + ick] = a[j];}a[j + ick] = temp;}for(i = 0; i < limit; i ++){cout<<a[i]<<" ";}cout<<endl;
}
int main()
{int a[50];int cnt = 0;for(cnt = 0; ;cnt ++){cin>>a[cnt];if(a[cnt] == 0) break;}int ick[10];int i = 0;while(cin>>ick[i]){i ++;}int j = 0;while(1){ShellSort(a, ick[j], cnt); //cnt取不到j ++;if(j == i) break;}return 0;
}

堆排序

【问题描述】请用堆排序的方法对一组数据进行排序，并给出建堆以及每一趟堆排序的结果。
【输入形式】一组数据，以0作为输入的结束。
【输出形式】建大根堆的结果，以及每一趟堆排序的结果。
【样例输入】

8 3 6 1 68 12 0

【样例输出】

68 8 12 1 3 6
12 8 6 1 3 68
8 3 6 1 12 68
6 3 1 8 12 68
3 1 6 8 12 68
1 3 6 8 12 68

【样例输入】

12 9 26 11 38 52 99 27 66 15 32 0

【样例输出】

99 66 52 27 38 12 26 9 11 15 32
66 38 52 27 32 12 26 9 11 15 99
52 38 26 27 32 12 15 9 11 66 99
38 32 26 27 11 12 15 9 52 66 99
32 27 26 9 11 12 15 38 52 66 99
27 15 26 9 11 12 32 38 52 66 99
26 15 12 9 11 27 32 38 52 66 99
15 11 12 9 26 27 32 38 52 66 99
12 11 9 15 26 27 32 38 52 66 99
11 9 12 15 26 27 32 38 52 66 99
9 11 12 15 26 27 32 38 52 66 99

#include<iostream>
using namespace std;int a[30];
int limit = 0; //limit为数组最后一个元素下标void Sift(int pos, int edge = limit)
{while(1){if(2 * pos + 2 <= edge){if(a[pos] > a[2 * pos + 1] && a[pos] > a[2 * pos + 2])break;if(a[pos * 2 + 1] < a[pos * 2 + 2]){swap(a[pos], a[pos * 2 + 2]);pos = pos * 2 + 2;continue;}else{swap(a[pos], a[pos * 2 + 1]);pos = pos * 2 + 1;continue;}}else if(2 * pos + 1 <= edge){if(a[pos] < a[pos * 2 + 1]){swap(a[pos], a[pos * 2 + 1]);pos = pos * 2 + 1;continue;}}if(2 * pos + 2 > edge ) break;}
}void HeapSort() //堆排序，limit可取，建立大根堆
{//建堆时，要将数据初始化成一个大根堆int i = 0;for(i = (limit - 1) / 2; i >= 0; i --) //初次建堆{if(i * 2 + 2 <= limit){if(a[i] < a[i * 2 + 1] || a[i] < a[i * 2 + 2]){if(a[i * 2 + 1] < a[i * 2 + 2]){swap(a[i], a[i * 2 + 2]);Sift(i * 2 + 2);}else{swap(a[i], a[i * 2 + 1]);Sift(i * 2 + 1);}}}else if(i * 2 + 1 <= limit){if(a[i] < a[i * 2 + 1]){swap(a[i], a[i * 2 + 1]);Sift(i * 2 + 1);}}}for(i  = 0; i <= limit; i ++) //输出第一次建堆后的结果{cout<<a[i]<<" ";}cout<<endl;for(i = limit; i > 0; i --){swap(a[i], a[0]);Sift(0, i - 1);int j;for(j = 0; j <= limit; j ++){cout<<a[j]<<" ";}cout<<endl;}
}
int main()
{int i = 0;for(i = 0; ; i ++){cin>>a[i];if(a[i] == 0)break;}limit = i - 1;HeapSort();return 0;
}

快速排序

【问题描述】输入一组数据，以0作为输入的结束，分别采用冒泡排序、选择排序、快速排序的方法，对其进行从小到大的排序，给出排序后的结果。

【输入形式】一组数据，以0作为输入的结束

【输出形式】三种排序后的结果

【样例输入】

9 8 4 5 7 2 10 6 0
【样例输出】

2 4 5 6 7 8 9 10

2 4 5 6 7 8 9 10

2 4 5 6 7 8 9 10

#include<iostream>
using namespace std;void PopSort(int a[], int limit)
{int i, j;for(i = limit - 1; i > 0; i --) //i 从最后一个元素取{int flag = 1;for(j = 0; j < i; j ++) //j只能取到i的前一位，因为还有j + 1{if(a[j] > a[j + 1]){int temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;flag = 0;}}if(flag) break;}for(i = 0; i < limit; i ++){cout<<a[i]<<" ";}cout<<endl;
}void QSort(int a[], int left, int right, int limit)
{while(left < right) //中间轴值就是a[left]{while(left < right && a[left] <= a[right]){right --;}swap(a[left], a[right]); // 轴值换成了a[right]while(left < right && a[left] <= a[right]){left ++;}swap(a[left], a[right]);}int i = 0;for(i = 0; i <limit; i ++){cout<<a[i]<<" ";}cout<<endl;
}void SelectSort(int a[], int limit)
{int i, j, k;for(i = 0; i < limit - 1; i ++){k = i;for(j = i + 1; j < limit; j ++){if(a[j] < a[k])k = j;}if(k != i)swap(a[i], a[k]);}for(i = 0; i < limit; i ++){cout<<a[i]<<" ";}cout<<endl;
}int main()
{int limit = 0;int a[20];for(limit = 0; ; limit ++){cin>>a[limit];if(a[limit] == 0) break;}PopSort(a, limit);SelectSort(a, limit);QSort(a, 0, limit - 1, limit);return 0;
}