沒有加什麼模板之類的,全用的int型,下標有的從0開始有的從1開始
1.插入
[cpp]
#include <iostream>
#include <cstdio>
#define N 1005
using namespace std;
int n, a[N];
void InsertSort(int a[], int n) //下標從0開始
{
int i, j, temp;
for(i = 1; i < n; i++)
{
temp = a[i];
for(j = i; j > 0 && temp < a[j - 1]; j--) a[j] = a[j - 1];
a[j] = temp;
}
}
int main()
{
int i;
scanf("%d", &n);
for(i = 0; i < n; i++) scanf("%d", &a[i]);
InsertSort(a, n);
for(i = 0; i < n; i++) printf("%d\n", a[i]);
return 0;
}
2.選擇
[cpp]
#include <iostream>
using namespace std;
int a[105];
//下標從1開始
void SelectSort(int a[], int n)
{
int i, j, pos;
for(i = 1; i < n; i++)
{
pos = i;
for(j = i; j <= n; j++)
{
if(a[j] < a[pos])
pos = j;
}
int temp = a[pos];
a[pos] = a[i];
a[i] = temp;
}
}
int main()
{
int n, i;
cin >> n;
for(i = 1; i <= n; i++) cin >> a[i];
SelectSort(a, n);
for(i = 1; i <= n; i++)
cout << a[i] << " ";
cout << endl;
return 0;
}
3.冒泡
[cpp]
#include <iostream>
using namespace std;
int a[105];
//下標從1開始
void BubbleSort(int a[], int n)
{
int i, j;
for(i = 1; i < n; i++)
{
for(j = 1; j <= n - i; j++)
{
if(a[j] > a[j + 1])
{
int temp = a[j + 1];
a[j + 1] = a[j];
a[j] = temp;
}
}
}
}
int main()
{
int n, i;
cin >> n;
for(i = 1; i <= n; i++)
cin >> a[i];
BubbleSort(a, n);
for(i = 1; i <= n; i++)
cout << a[i] << " ";
cout << endl;
return 0;
}
4.快排
[cpp]
#include <iostream>
using namespace std;
int n;
int a[105];
//下標從0開始
int partition(int a[], int low, int high)
{//快速排序中的一趟
int key;//作為樞軸來使用
key = a[low];
while(low < high)
{
while(low < high && a[high] >= key)
--high;
a[low] = a[high];
while(low < high && a[low] <= key)
++low;
a[high] = a[low];
}
a[low] = key;
return low;
}
void qsort(int a[], int low, int high)
{//快速排序的遞歸形式
int loc;
if(low < high)
{
loc = partition(a, low, high);//一趟排序結果的調用
qsort(a, low, loc - 1);
qsort(a, loc + 1, high);
}
}
int main()
{
int i;
cin >> n;
for(i = 0; i < n; i++) cin >> a[i];
qsort(a, 0, n - 1);
for(i = 0; i < n; i++) cout << a[i] << " ";
cout << endl;
return 0;
}
5.歸並
[cpp]
#include <iostream>
#define N 105
using namespace std;
int n;
int a[N], t[N];
/* 歸並 */
//下標從0開始
void Merge(int a[], int l, int m, int r)
{
/* p指向輸出區間 */
int p = 0;
/* i、j指向2個輸入區間 */
int i = l, j = m + 1;
/* 2個輸入區間都不為空時 */
while(i <= m && j <= r)
{/* 取關鍵字小的記錄轉移至輸出區間 */
if (a[i] > a[j])
t[p++] = a[j++];
else
t[p++] = a[i++];
}
/* 將非空的輸入區間轉移至輸出區間 */
while(i <= m) t[p++] = a[i++];
while(j <= r) t[p++] = a[j++];
/* 歸並完成後將結果復制到原輸入數組 */
for (i = 0; i < p; i++)
a[l + i] = t[i];
}
/* 歸並排序 */
void MergeSort(int a[], int l, int r)
{
int m;
if (l < r)
{/* 將長度為n的輸入序列分成兩個長度為n/2的子序列 */
m = (l + r) / 2;
/* 對兩個子序列分別進行歸並排序 */
MergeSort(a, l, m);
MergeSort(a, m + 1, r);
/* 將2個排好的子序列合並成最終有序序列 */
Merge(a, l, m, r);
}
}
int main()
{
int i;
cin >> n;
for(i = 0; i < n; i++) cin >> a[i];
MergeSort(a, 0, n - 1);
for(i = 0; i < n; i++) cout << a[i] << " ";
cout << endl;
return 0;
}
6.堆排
[cpp]
#include <iostream>
using namespace std;
int n;
int a[105];
//下標從1開始
void HeapAdjust(int A[], int a, int z)
{
int i, j;
for(i = a, j = 2 * i; j <= z; i = j, j = 2 * i)
{ //i為父,j為子
if(j < z && A[j + 1] > A[j]) j++; //大頂堆,沿大孩子方向下行
if(A[i] < A[j])
swap(A[i], A[j]);
else break;
}
}
void HeapSort(int A[], int n)
{
int i;
for(i = n / 2; i >= 1; i--) //從倒數第一個非葉子結點,自下而上堆化
HeapAdjust(A, i, n);
for(i = n; i > 1; i--)
{ //交換A[1]與最後元素A[i](i=n, ..., 1), 再堆化
swap(A[1], A[i]);
HeapAdjust(A, 1, i - 1);
}
}
int main()
{
int i;
cin >> n;
for(i = 1; i <= n; i++)
cin >> a[i];
HeapSort(a, n);
for(i = 1; i <= n; i++) cout << a[i] << " ";
cout << endl;
return 0;
}
作者:sdj222555