SCAU 數據結構實驗六排序算法

在這里插入圖片描述
![[Pasted image 20240

8638 直接插入排序

Description

用函數實現直接插入排序，并輸出每趟排序的結果.

輸入格式

第一行：鍵盤輸入待排序關鍵的個數n
第二行：輸入n個待排序關鍵字，用空格分隔數據

輸出格式

每行輸出一趟排序結果，數據之間用一個空格分隔

輸入樣例

10
5 4 8 0 9 3 2 6 7 1

輸出樣例

4 5 8 0 9 3 2 6 7 1
4 5 8 0 9 3 2 6 7 1
0 4 5 8 9 3 2 6 7 1
0 4 5 8 9 3 2 6 7 1
0 3 4 5 8 9 2 6 7 1
0 2 3 4 5 8 9 6 7 1
0 2 3 4 5 6 8 9 7 1
0 2 3 4 5 6 7 8 9 1
0 1 2 3 4 5 6 7 8 9
在這里插入圖片描述

1.插入排序：在原有的序列基礎上，一次插入一個元素
2.插入排序是一種穩定的排序算法，如果碰見一個和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。
3.時間復雜度為 O(n^2)，在最壞情況下需要進行 n*(n-1)/2 次比較和移動操作。

#include<iostream>
using namespace std;int main()
{int n,i,j,k;cin >> n;int a[n+5];for(i=1;i<=n;i++)   cin >> a[i];//輸入for(i=2;i<=n;i++){//如果未排序的比已排序的最大的那個數要小
//例如括號內的是已排序的（13，38，49，65,76,97）27，
//這里就是97比27要大，需要排序if(a[i]<a[i-1]){a[0]=a[i];//把要排序的那個27保存起來//a[i]=a[i-1];//27的位置放置97這個數字，此時的情況是（13，38，49，65,76，97）,97for(j=i-1;a[0]<a[j];j--)//全部往后移，為要插入的數騰出空間，最后是（13，38，38，49,65，76）,97a[j+1]=a[j];a[j+1]=a[0];//把暫存的27放到第一個38的位置}for(int k=1;k<=n;k++)   cout << a[k] << " ";cout << endl;}return 0;
}

8639 折半插入排序

Description

用函數實現折半插入排序，并輸出每趟排序的結果.

輸入格式

第一行：鍵盤輸入待排序關鍵的個數n
第二行：輸入n個待排序關鍵字，用空格分隔數據

輸出格式

每行輸出一趟排序結果，數據之間用一個空格分隔

輸入樣例

10
5 4 8 0 9 3 2 6 7 1

輸出樣例

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

#include<iostream>
#include<algorithm>
using namespace std;int d[200000];  // 定義一個足夠大的數組// 遍歷函數，用于輸出數組中的元素
void Travers(int n) {for(int i = 1; i <= n; i++) {cout << d[i] << " ";}cout << endl;
}int main() {int n;cin >> n;  // 讀取數組的元素數量// 將元素輸入到數組中，從下標1開始for(int i = 1; i <= n; i++) {cin >> d[i];}int low, high, mid;// 從第二個元素開始進行插入排序for(int i = 2; i <= n; i++) {d[0] = d[i];  // 將當前元素暫存到哨兵位置d[0]low = 1;high = i - 1;// 二分查找插入位置while(low <= high) {mid = (low + high) / 2;  // 計算中間位置if(d[0] < d[mid]) {high = mid - 1;  // 如果待插入元素小于中間元素，在左半部分查找} else {low = mid + 1;  // 如果待插入元素大于等于中間元素，在右半部分查找}}// 將元素右移，為插入元素騰出位置for(int j = i - 1; j >= high + 1; j--) {d[j + 1] = d[j];}// 將暫存的哨兵元素插入到正確位置d[high + 1] = d[0];// 每趟排序后輸出數組的當前狀態Travers(n);}return 0;
}

8640 希爾(shell)排序

Description

用函數實現希爾(shell)排序，并輸出每趟排序的結果,初始增量d=n/2,其后d=d/2

輸入格式

第一行：鍵盤輸入待排序關鍵的個數n
第二行：輸入n個待排序關鍵字，用空格分隔數據

輸出格式

每行輸出一趟排序結果，數據之間用一個空格分隔

輸入樣例

10
5 4 8 0 9 3 2 6 7 1

輸出樣例

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

在這里插入圖片描述

1.希爾排序：插入排序的升級版
當剛開始元素很無序的時候，增量最大，所以插入排序的元素個數很少，速度很快；當元素基本有序了，增量很小，插入排序對于有序的序列效率很高。
2.不穩定：3 5 1 5 0 8
第一個5會交換到第二個5后面

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <malloc.h>
#include <algorithm>
#include <vector>
using namespace std;int n, a[100005];// 打印數組函數
void print()
{for (int i = 0; i < n; i++)  // 從下標0到n-1輸出數組元素cout << a[i] << ' ';cout << endl;
}// 希爾排序函數
void shellSort() {for (int gap = n / 2; gap > 0; gap /= 2) {  // 初始化步長為數組長度的一半，逐次減半for (int i = gap; i < n; i++) {  // 從當前步長開始遍歷數組for (int j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap) {  // 插入排序，將元素按步長間隔進行比較和交換swap(a[j], a[j + gap]);  // 交換元素位置}}print();  // 每次步長變化后打印數組}
}int main()
{cin >> n;  // 輸入數組長度for (int i = 0; i < n; i++)  // 輸入數組元素cin >> a[i];shellSort();  // 調用希爾排序函數return 0;  // 程序結束
}

8641 冒泡排序

Description

用函數實現冒泡排序，并輸出每趟排序的結果(要求當一趟冒泡過程中不再有數據交換，則排序結束)

輸入格式

第一行：鍵盤輸入待排序關鍵的個數n
第二行：輸入n個待排序關鍵字，用空格分隔數據

輸出格式

每行輸出每趟排序結果，數據之間用一個空格分隔

輸入樣例

10
5 4 8 0 9 3 2 6 7 1

輸出樣例

4 5 0 8 3 2 6 7 1 9
4 0 5 3 2 6 7 1 8 9
0 4 3 2 5 6 1 7 8 9
0 3 2 4 5 1 6 7 8 9
0 2 3 4 1 5 6 7 8 9
0 2 3 1 4 5 6 7 8 9
0 2 1 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
在這里插入圖片描述
冒泡：
1.元素倆倆比較，將大的元素向后調，若元素大小相等，則不交換，所以是穩定排序
2.雙重循環：
時間復雜度O(n^2)
空間復雜度O(1)
3.注意flag判斷是否發生交換


#include <iostream>
#include <queue>
#include<cstring>
using namespace std;
const int N = 550, M = 10010; 
int a[N];int main()
{int n;cin >> n;for (int i = 0; i < n; i++)cin >> a[i];for (int i = 0; i < n; i++){int mark = 1;for (int j = 0; j < n-i-1; j++)if (a[j+1] < a[j]){swap(a[j], a[j + 1]);mark = 0;}for (int k = 0; k < n; k++)cout << a[k]<<" ";cout << endl;//某一趟全部不交換才結束if (mark)break;//最后一趟也要輸出}return 0;
}

8642 快速排序

Description

用函數實現快速排序，并輸出每次分區后排序的結果

輸入格式

第一行：鍵盤輸入待排序關鍵的個數n
第二行：輸入n個待排序關鍵字，用空格分隔數據

輸出格式

每行輸出每趟排序的結果，數據之間用一個空格分隔

輸入樣例

10
5 4 8 0 9 3 2 6 7 1

輸出樣例

1 4 2 0 3 5 9 6 7 8
0 1 2 4 3 5 9 6 7 8
0 1 2 4 3 5 9 6 7 8
0 1 2 3 4 5 9 6 7 8
0 1 2 3 4 5 8 6 7 9
0 1 2 3 4 5 7 6 8 9
0 1 2 3 4 5 6 7 8 9
![[Pasted image 20240605143858.png]] 在這里插入圖片描述
1.快排：雙指針在左右兩側，若右指針所指向的元素比中樞小，則將左指針指向的值賦值未右指針指向的值。移動左指針，同理；
2.不穩定：5 3 3 4 3 8 9 10 11
3.時間復雜度：O（nlogn）

#include <iostream>
#include <cstdio>
using namespace std;// 定義常量 N 表示數組最大長度
const int N = 1000;// 定義數組 q 和變量 n
int q[N];
int n;// 快速排序函數
void sort(int q[], int l, int r) {// 基準條件：如果子數組長度為 0 或 1，則不需要排序if (l >= r) return;// 選擇樞軸元素 x，并初始化左右指針 i 和 jint x = q[l], i = l, j = r;// 分區操作while (i < j) {// 從右向左掃描，找到第一個小于樞軸 x 的元素while (i < j && q[j] >= x) j--;// 將該元素放到左側位置q[i] = q[j];// 從左向右掃描，找到第一個大于樞軸 x 的元素while (i < j && q[i] <= x) i++;// 將該元素放到右側位置q[j] = q[i];}// 將樞軸元素放到正確位置q[i] = x;// 輸出當前排序結果，用于調試for (int i = 0; i < n; i++) cout << q[i] << ' ';cout << endl;// 對左右子數組遞歸排序sort(q, l, j - 1);sort(q, j + 1, r);
}// 主函數
int main() {// 輸入數組長度 ncin >> n;// 輸入數組元素for (int i = 0; i < n; i++) cin >> q[i];// 調用快速排序函數sort(q, 0, n - 1);// 返回 0 表示程序正常結束return 0;
}

8643 簡單選擇排序

Description

用函數實現簡單選擇排序，并輸出每趟排序的結果

輸入格式

第一行：鍵盤輸入待排序關鍵的個數n
第二行：輸入n個待排序關鍵字，用空格分隔數據

輸出格式

每行輸出每趟排序的結果，數據之間用一個空格分隔

輸入樣例

10
5 4 8 0 9 3 2 6 7 1

輸出樣例

0 4 8 5 9 3 2 6 7 1
0 1 8 5 9 3 2 6 7 4
0 1 2 5 9 3 8 6 7 4
0 1 2 3 9 5 8 6 7 4
0 1 2 3 4 5 8 6 7 9
0 1 2 3 4 5 8 6 7 9
0 1 2 3 4 5 6 8 7 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
在這里插入圖片描述
1.選擇排序：給每個位置選存在的最小值
2.選擇排序不穩定：舉個例子 5 8 5 2 9，
3.時間復雜度：O（n^2）空間復雜度：O（1）；

//選擇排序 
void SelectSort(int a[], int n){for(int i = 0; i < n; i ++){int min = i;//min記錄最下元素的下標 for(int j = i; j < n; j ++){if(a[j] < a[min]) min = j;}if(min != i) swap(a[i], a[min]);//交換兩個值 }
}

8644 堆排序

Description

用函數實現堆排序，并輸出每趟排序的結果

輸入格式

第一行：鍵盤輸入待排序關鍵的個數n
第二行：輸入n個待排序關鍵字，用空格分隔數據

輸出格式

第一行：初始建堆后的結果
其后各行輸出交換堆頂元素并調整堆的結果，數據之間用一個空格分隔

輸入樣例

10
5 4 8 0 9 3 2 6 7 1

輸出樣例

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

代碼1

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>using namespace std;int n, a[100005];void print()
{for (int i = 1; i <= n; i++)cout << a[i] << ' ';cout << endl;
}void HeapAdjust(int Start, int End)//將a[S...E]調整為以a[S]為根的大根堆
{int dad = Start;int son = dad * 2;while (son <= End)//子結點在范圍內才能進行比較{if (son + 1 <= End && a[son] < a[son + 1])son++;//選擇大的子結點if (a[dad] > a[son])return;else{swap(a[dad], a[son]);dad = son;son = dad * 2;}}
}void HeapSort()
{for (int i = n / 2; i >= 1; i--){HeapAdjust(i, n);//初建堆}print();for (int i = n; i > 1; i--){swap(a[1], a[i]);HeapAdjust(1, i - 1);print();//輸出調整堆的結果}
}int main()
{cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];HeapSort();return 0;
}

代碼2

#include <iostream>
using namespace std;const int N = 1000;
int a[N];
int n; // 堆的大小// 向下調整函數：調整堆
void down(int len,int u) {int t = u;if (2 * u <= len && a[2 * u] > a[t]) t = 2 * u;if (2 * u + 1 <= len && a[2 * u + 1] > a[t]) t = 2 * u + 1;if (t != u) {swap(a[t], a[u]);down(len,t);}
}
void heapSort(int len) {// 建堆for (int i = len / 2; i >= 1; i--) down(len, i);// 輸出初始堆for (int i = 1; i <= len; i++) cout << a[i] << ' ';cout << endl;// 排序過程for (int i = 1; i < len; i++) {swap(a[1], a[len - i + 1]); // 將堆頂元素（最大值）交換到數組末尾down(len - i, 1); // 對剩余堆進行調整// 輸出調整后的堆for (int j = 1; j <= n; j++) cout << a[j] << ' ';cout << endl;}
}int main() {cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];heapSort(n);// 輸出排序后的數組return 0;
}

8645 歸并排序（非遞歸算法）

Description

用函數實現歸并排序（非遞歸算法），并輸出每趟排序的結果

輸入格式

第一行：鍵盤輸入待排序關鍵的個數n
第二行：輸入n個待排序關鍵字，用空格分隔數據

輸出格式

每行輸出每趟排序的結果，數據之間用一個空格分隔

輸入樣例

10
5 4 8 0 9 3 2 6 7 1

輸出樣例

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

在這里插入圖片描述
1.非遞歸的歸并排序：
先將n個元素按順序劃分為n/2組（n為奇數，則最后一個為一組）
每一組在組內進行排序
將相鄰的兩個組一一合并在排序
不斷重復直到完成排序
2.穩定：合并過程中我們可以保證如果兩個當前元素相等時，我們把處在前面的序列的元素保存在結果序列的前面
3.時間復雜度O（nlogn）

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 1010;
int len;
int arr[N], temp[N];void merge(int arr[], int l, int mid, int r)
{int k = 0, i = l, j = mid + 1;// 合并兩個有序子數組while (i <= mid && j <= r){if (arr[i] < arr[j])temp[k++] = arr[i++];elsetemp[k++] = arr[j++];}while (i <= mid)temp[k++] = arr[i++];while (j <= r)temp[k++] = arr[j++];// 將合并后的數組復制回原數組for (i = l, j = 0; i <= r; i++, j++)arr[i] = temp[j];
}void merge_sort(int arr[], int len)
{// 迭代合并的步長從 1 開始for (int step = 1; step < len; step *= 2){// 每個步長內進行合并for (int i = 1; i <= len; i += 2 * step){int mid = i + step - 1;int r = min(i + 2 * step - 1, len);merge(arr, i, mid, r);}// 輸出排序后的數組for (int i = 1; i <= len; i++)cout << arr[i] << " ";cout << endl;}
}int main()
{cin >> len;for (int i = 1; i <= len; i++)cin >> arr[i];// 調用歸并排序算法對數組進行排序merge_sort(arr, len);return 0;
}

8646 基數排序

Description

用函數實現基數排序，并輸出每次分配收集后排序的結果

輸入格式

第一行：鍵盤輸入待排序關鍵的個數n
第二行：輸入n個待排序關鍵字，用空格分隔數據

輸出格式

每行輸出每趟每次分配收集后排序的結果，數據之間用一個空格分隔

輸入樣例

10
278 109 063 930 589 184 505 069 008 083

輸出樣例

930 063 083 184 505 278 008 109 589 069
505 008 109 930 063 069 278 083 184 589
008 063 069 083 109 184 278 505 589 930
在這里插入圖片描述
1.穩定
2.時間復雜度：O（n * k）
k為位數

#include <iostream>
#include <algorithm>
using namespace std;int x=1;  //用于算每個位數的值bool cmp(int a,int b)
{a/=x;b/=x;if(a%10<b%10) //當前要比較的值比較小的靠前return true;return false;
}int main()
{int n;cin>>n;int a[n];for(int i=0;i<n;i++)scanf("%d",&a[i]);while(x<=100){sort(a,a+n,cmp);for(int i=0;i<n;i++)printf("%03d ",a[i]);  //按格式輸出printf("\n");x*=10;  //每次要求的位數乘10}return 0;
}