A）需求分析：
1、冒泡排序
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上 而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较 小的往上冒。
冒泡排序是稳定的。算法时间复杂度O(n2)--[n的平方]
2、选择排序
在要排序的一组数中，选出最小的一个数与第一个位置的数交换； 然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环 到倒数第二个数和最后一个数比较为止。
选择排序是不稳定的。算法复杂度O(n2)--[n的平方]
3、插入排序
直接插入排序是稳定的。算法时间复杂度O(n2)--[n的平方]
4、折半插入排序
折半插入排序是对插入排序的改进，主要通过二分查找，获得插入的位置 折半插入是一种稳定的排序 排序时间复杂度O(n^2)附加空间O(1)
5、快速排序
快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n2)
6、希尔排序
算法先将要排序的一组数按某个增量d分成若干组，每组中
记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量 对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成 一组，排序完成。
7、堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素 交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数
实现排序的函数。有最大堆和最少堆之分
堆排序是不稳定的。算法时间复杂度O(nlog2n)。
8、归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
归并排序是一种较稳定的排序 时间复杂度为时间O(nlogn)
9、基数排序
基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
基数排序是一种不稳定的排序，时间复杂度为：O(d(n+radix))
B）概要设计：
void insertsort(int *a );//插入排序函数
void Binsertsort(int *a ); //折半插入排序函数
void bubble_sort(int *a); //冒泡排序
void quick_sort(int *a , int low , int high) ;//快速排序
int one_quick_sort(int *a , int low , int high) ; //一趟快速排序
void select_sort(int *a); //直接选择排序
void merge_sort(int *a , int low , int high); //归并排序
void msort(int *a , int low , int high,int mid); //归并排序调用函数
void head_sort(int *a); //堆排序函数
void head_adgust(int *a , int low , int high); // 堆排序调用函数
int max_select_sort(int *a, int t); //选择最大数
void shell_insert(int *a , int dk); //希尔排序调用函数 void shell_sort(int *a); //希尔排序函数
void dadix_sort(int *a); //技术排序函数
int cmp1(int a,int b); //sort()函数里面的比较函数
int cmp2(int a,int b); //sort()函数里面的比较函数
void rand_sort(int *a) ; //随机产生函数
void display(int *a) ; //打印数组
C）详细设计：
// 12.cpp : Defines the entry point for the console application. //
#include "stdafx.h"
#include "stdlib.h"
#include "time.h"
#include <iostream>
#include <algorithm>
using namespace std;
int a[15]; //排序数组
int len = 15 ; //数组长度
void insertsort(int *a ); //插入排序函数
void Binsertsort(int *a ); //折半插入排序函数 void bubble_sort(int *a); //冒泡排序
void quick_sort(int *a , int low , int high) ; //快速排序 int one_quick_sort(int *a , int low , int high) ; //一趟快速排序
void select_sort(int *a); //直接选择排序
void merge_sort(int *a , int low , int high); //归并排序
void msort(int *a , int low , int high,int mid); //归并排序调用函数
void head_sort(int *a); //堆排序函数 void head_adgust(int *a , int low , int high); // 堆排序调
用函数
int max_select_sort(int *a, int t); //选择最大数
void shell_insert(int *a , int dk); //希尔排序调用函数
void shell_sort(int *a); //希尔排序函数 void dadix_sort(int *a); //技术排序函数
int cmp1(int a,int b); //sort()函数里面的比较函数
int cmp2(int a,int b); //sort()函数里面的比较函数
void rand_sort(int *a) ; //随机产生函数
void display(int *a) ; //打印数组
int main(int argc, char* argv[])
{
srand(unsigned(time(NULL))); //产生随即种子
cout<<" ******* 1.插入排序*********"<<endl;
cout<<"随机产生数据:"<<endl;
rand_sort(a);
display(a);
cout<<"排序之后的数据"<<endl;
insertsort(a);
display(a);
cout<<endl;
cout<<" ******* 2.折半插入排序*********"<<endl; cout<<"随机产生数据:"<<endl;
rand_sort(a);
display(a);
cout<<"排序之后的数据"<<endl;
Binsertsort(a);
display(a);
cout<<endl;
cout<<" ******* 3.冒泡排序*********"<<endl;
cout<<"随机产生数据:"<<endl;
rand_sort(a);
display(a);
cout<<"排序之后的数据"<<endl;
bubble_sort(a);
display(a);
cout<<endl;
cout<<" ******* 4.快速排序*********"<<endl; cout<<"随机产生数据:"<<endl; rand_sort(a); display(a); cout<<"排序之后的数据"<<endl; quick_sort(a, 0 ,len-1); display(a); cout<<endl; cout<<" ******* 5.选择排序*********"<<endl; cout<<"随机产生数据:"<<endl; rand_sort(a); display(a); cout<<"排序之后的函数"<<endl; select_sort(a); display(a); cout<<endl; cout<<" ******* 6.归并排序*********"<<endl; cout<<"随机产生数据:"<<endl; rand_sort(a); display(a); cout<<"排序之后的数据"<<endl; merge_sort(a , 0 , len); display(a); cout<<endl; cout<<" ******* 7.堆排序*********"<<endl; cout<<"随机产生数据:"<<endl; rand_sort(a); display(a); cout<<"排序之后的数据"<<endl; head_sort(a ); display(a); cout<<endl; cout<<" ******* 8.希尔排序*********"<<endl; cout<<"随机产生数据:"<<endl; rand_sort(a); display(a); cout<<"排序之后的数据"<<endl; shell_sort(a); display(a); cout<<endl;
cout<<" ******* 9.基数排序*********"<<endl; cout<<"随机产生数据:"<<endl;
rand_sort(a);
display(a);
cout<<"排序之后的数据"<<endl;
dadix_sort(a);
display(a);
cout<<endl;
return 0;
}
void insertsort(int *a )
{
int temp;
for (int i = 1 ; i < len ; ++i )
{
if (a[i - 1] > a[i])
{
temp = a[i];
a[i] = a[i-1];
for (int j = i - 1 ; temp < a[j] ; --j ) {
a[j+1] = a[j];
}
a[j+1] = temp;
}
}
}
void Binsertsort(int *a ) //折半插入排序函数 {
int temp;
int low,high,mid;
for (int i = 1 ; i < len ; ++i )
{
temp = a[i];
low = 0 ;
high = i- 1 ;
while (low <= high)
{
mid = (low + high ) / 2 ;
if ( temp < a[mid])
{
high = mid -1 ;
}
else
low = mid+1;
}
for (int j = i - 1 ; j > high ; --j )
{
a[j+1] = a[j];
}
a[j+1] = temp ;
}
}
void bubble_sort(int *a) //冒泡排序
{
int temp;
for (int i = 1 ; i < len ; ++i )
{
for (int j = 0 ; j < len - i ; ++j )
{
if (a[j] > a[j+1] )
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp ;
}
}
}
}
void quick_sort(int *a , int low , int high) //快速排序 {
if (low < high )
{
int mid;
mid = one_quick_sort(a , low , high );
quick_sort(a , low , mid - 1 );
quick_sort(a , mid+1 , high );
}
}
int one_quick_sort(int *a , int low , int high) //一趟快速排序 {
int temp;
while (low < high )
{
while ( a[low ] <= a[high] && low < high )
{
--high;
}
temp = a[low];
a[low] = a[high];
a[high] = temp ;
while (a[low] <= a[high] && low <high )
{
++low;
}
temp = a[high] ;
a[high] = a[low];
a[low] = temp;
}
return low;
}
void select_sort(int *a) //直接选择排序 {
int n,temp;
int t = len - 1 ;
for (int j = len - 1 ; j >= 0 ; --j,--t )
{
n = max_select_sort(a , t);
if (j != n )
{
temp = a[n];
a[n] = a[j];
a[j] = temp ;
}
}
}
int max_select_sort(int *a, int t) //选择最大数 {
int temp = a[0];
int flag = 0 ;
for (int i = 0 ; i <= t; ++i )
{
if (a[i] > temp )
{
temp = a[i];
flag = i ;
}
}
return flag;
}
void merge_sort(int *a , int low , int high) {
if (low < high)
{
int mid = (low + high) / 2 ;
merge_sort(a , low , mid);
merge_sort(a , mid + 1 , high); msort(a , low , high , mid);
}
}
void msort(int *a , int low , int high,int mid) 数
{
int i = low,j = mid+1,*b,r = 0;
b = new int[high - low];
while(i <= mid && j <= high)
{
if (a[i] <= a[j])
{
b[r] = a[i];
++r ;
++i;
}
else
{
b[r] = a[j];
++j;
++r;
}
}
while (i <= mid )
{
b[r] = a[i];
++r;
++i ;
}
while (j <= high)
{
b[r] = a[j];
++j;
++r ;
}
for (i = low ,j = 0 ; i <= high ; ++i ,++j ) { //归并排序 //归并排序调用函
a[i] = b[j];
}
}
void head_sort(int *a) //推排序
{
int temp ;
for (int i = len / 2 - 1 ; i>= 0 ; --i )
{
head_adgust(a , i , len);
}
for ( i = len - 1 ; i >= 0 ; --i )
{
temp = a[0];
a[0] = a[i];
a[i] = temp;
head_adgust(a , 0 , i - 1 );
}
}
void head_adgust(int *a , int low , int high) //调整的最大堆 {
int temp ;
for (int i = 2 * low + 1 ; i < high ; i = i * 2 +1 ) {
if (a[i] < a[i+1])
{
++i;
}
if (a[low] > a[i])
{
break;
}
else
{
temp = a[low];
a[low] = a[i];
a[i] = temp;
low = i ;
}
}
}
void shell_insert(int *a , int dk) 希尔插入函数 {
int temp;
for (int i = dk ; i < len ; ++i )
{
if (a[i] < a[i-dk])
{
temp = a[i];
for (int j = i - dk ; j >= 0 && temp < a[j] ; j = j-dk ) {
a[j+dk] = a[j];
}
a[j+dk] = temp ;
}
}
}
void shell_sort(int *a) //希尔排序
{
int dks[3] = { 4 ,3, 1}; //定义步长
for (int i = 0 ; i < 3 ; ++i )
{
shell_insert(a , dks[i]);
}
}
void dadix_sort(int *a) //基数排序
{
sort(a , a + 15 , cmp2);
sort(a , a + 15 , cmp1);
}
int cmp1(int a,int b) //个位数比较函数
{
if (a / 10 < b /10)
{
return 1;
}
return 0;
}
int cmp2(int a,int b) //十位数比较函数
{
if (a % 10 < b % 10 )
{
return 1;
}
return 0;
}
void rand_sort(int *a) //产生随机数据函数
{
for (int i = 0 ; i < len ; ++i )
{
a[i] = rand()%100;
}
}
void display(int *a) //打印排序好之后的函数
{
for (int i = 0 ; i < len ; ++i )
{
cout<<a[i] << " ";
}
cout<<endl;
}
D）调试分析;
1、测试数据：测试数据主要通过函数rang_sort()，自动生成一系列数据
2、各个模块 分别测试，1-9分别测试了9种排序
E）课程总结：
通过数据结构大型作业，算法主要在于思想，以及思路的严谨性。实战型很强。通过练习，编程能力以及算法思想大大提高。
一插入排序InsertionSort1基本思想每次将一个待排序的数据元素插入到前面已经排好序的数列中的适当位置使数列依然有序直到待…
数据结构各种排序算法总结计算机排序与人进行排序的不同计算机程序不能象人一样通览所有的数据只能根据计算机的quot比较quot原理在…
数据结构与算法总结姓名：**学号：**班级：12计本（2）班这个学期在老师的带领下我们学习了数据结构与算法这门课程。在本次数据结构…
排序总结排序方法平均时间最坏时间辅助存储简单排序O(n2)O(n2)O(1)快速排序O(nlogn)O(n2)O(logn)堆排序…
数据结构实验课程之手工执行一下排序算法写出每一趟排序结束时的关键码状态includeltstdiohgtincludeltstdl…
数据结构课程总结孙博110401104511计本3班如何合理的组织数据、高效的处理数据是扩大计算机应用领域、提高软件效率的关键。而…
《数据结构与算法》课程学习总结报告070401301507计本（3）班张浩本学期开设的《数据结构与算法》课程已经告一段落，现就其知…
通过一学期对《数据结构与算法》的学习，大概的了解了基本的数据结构和相应的一些算法。下面总结一下自己一个学期学习的收获和心得。数据结…
排序总结排序方法平均时间最坏时间辅助存储简单排序O(n2)O(n2)O(1)快速排序O(nlogn)O(n2)O(logn)堆排序…
数据结构与算法学习心得不管学习什么，概念是基础，所有的知识框架都是建立在基础概念之上的。所以，第一遍看课本要将概念熟记于心，然后构…