数据结构——常用的内部排序算法

时间:2021-11-17 10:31:30

借鉴博客: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;
}