各类排序C++实现（冒泡，选择，插入，快排，归并，堆排）
没有加什么模板之类的，全用的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
