借鉴博客:http://blog.csdn.net/hguisu/article/details/7776068
目的:
1.掌握常见的内部排序算法的思想及其适用条件。
2.掌握常见的内部排序算法的程序实现。
内容:
输入一组关键字序列分别实现下列排序:
(1) 实现简单选择排序、直接插入排序和冒泡排序。
(2) 实现希尔排序算法。
(3) 实现快速排序算法。
(4) 实现堆排序算法。
(5) 在主函数中设计一个简单的菜单,分别测试上述算法。
代码(已由codeblocks编译通过,有错误欢迎大佬指正):
#include<bits/stdc++.h>
#define N 1009
using namespace std;
void menu()
{
cout << endl;
printf("\t\t\t1.简单选择排序\n");
printf("\t\t\t2.直接插入排序\n");
printf("\t\t\t3.冒泡排序\n");
printf("\t\t\t4.希尔排序\n");
printf("\t\t\t5.快速排序\n");
printf("\t\t\t6.堆排序\n");
printf("\t\t\t7.退出\n");
}
void Sel_sort()
{
int n, a[N], i, j;
scanf("%d", &n);
for(i = 1; i <= n; i++) scanf("%d", &a[i]);
for(i = 1; i <= n; i++)
{
for(j = i + 1; j <= n; j++)
{
if(a[i] > a[j]) swap(a[i], a[j]);
}
}
for(i = 1; i <= n; i++) printf("%d%c", a[i], i == n ? '\n' : ' ');
}
void Insert_sort()
{
int n, a[N], i, j, num;
scanf("%d", &n);
for(i = 1; i <= n; i++)
{
scanf("%d", &num);
int len = i;
for(j = 1; j < len; j++) if(a[j] > num) break;
int cur = j;
for(j = len; j > cur; j--) a[j] = a[j - 1];
a[cur] = num;
}
for(i = 1; i <= n; i++) printf("%d%c", a[i], i == n ? '\n' : ' ');
}
void Mp_sort()
{
int n, a[N], i, j;
scanf("%d", &n);
for(i = 1; i <= n; i++) scanf("%d", &a[i]);
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n-i; j++)
if(a[j] > a[j+1]) swap(a[j], a[j+1]);
}
for(i = 1; i <= n; i++) printf("%d%c", a[i], i == n ? '\n' : ' ');
}
void Shell_sort()
{
int n, a[N], i, j;
scanf("%d", &n);
for(i = 1; i <= n; i++) scanf("%d", &a[i]);
int dk = n>>1;
while(dk)
{
for(i = 1 + dk; i <= n; i++)
{
if(a[i] < a[i-dk])
{
j = i - dk;
int x = a[i];
while(j >= 1 && x < a[j])
{
a[j+dk] = a[j];
j -= dk;
}
a[j+dk] = x;
}
}
dk >>= 1;
}
for(i = 1; i <= n; i++) printf("%d%c", a[i], i == n ? '\n' : ' ');
}
int Partition(int a[], int low, int high)
{
int cur = a[low];
while(low < high)
{
while(low < high && a[high] > cur) high--;
swap(a[low], a[high]);
while(low < high && a[low] < cur) low++;
swap(a[low], a[high]);
}
return low;
}
void qq_sort(int a[], int low, int high)
{
if(low < high)
{
int mid = Partition(a, low, high);
qq_sort(a, low, mid - 1);
qq_sort(a, mid + 1, high);
}
}
void q_sort()
{
int n, a[N], i;
scanf("%d", &n);
for(i = 1; i <= n; i++) scanf("%d", &a[i]);
qq_sort(a, 1, n);
for(i = 1; i <= n; i++) printf("%d%c", a[i], i == n ? '\n' : ' ');
}
void heap_adjust(int a[], int pre, int n)
{
int child = pre * 2 + 1;
int tm = a[pre];
while(child < n)
{
if(child + 1 < n && a[child] < a[child+1]) child++;
if(a[pre] < a[child])
{
a[pre] = a[child];
pre = child;
child = pre * 2 + 1;
}
else break;
a[pre] = tm;
}
}
void Heap_sort()
{
int n, a[N], i;
scanf("%d", &n);
for(i = 0; i < n; i++) scanf("%d", &a[i]);
for(i = ((n - 1)>>1); i >= 0; i--) heap_adjust(a, i, n);
for(i = n - 1; i > 0; i--)
{
swap(a[i], a[0]);
heap_adjust(a, 0, i);
}
for(i = 0; i < n; i++) printf("%d%c", a[i], i == n ? '\n' : ' ');
}
int main()
{
while(true)
{
int sel;
menu();
scanf("%d", &sel);
switch(sel)
{
case 1: Sel_sort(); break;
case 2: Insert_sort(); break;
case 3: Mp_sort(); break;
case 4: Shell_sort(); break;
case 5: q_sort(); break;
case 6: Heap_sort(); break;
}
if(sel == 7) break;
}
return 0;
}