各类排序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
补充:软件开发 , C++ ,