数据结构中的各种排序.doc

A） 需求分析：1、冒泡排序在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。冒泡排序是稳定的。算法时间复杂度O(n2)-n的平方2、选择排序在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。 选择排序是不稳定的。算法复杂度O(n2)-n的平方3、插入排序直接插入排序是稳定的。算法时间复杂度O(n2)-n的平方4、折半插入排序折半插入排序是对插入排序的改进，主要通过二分查找，获得插入的位置折半插入是一种稳定的排序 排序时间复杂度O(n2)附加空间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 #include using namespace std;int a15; /排序数组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);coutendl;cout * 2.折半插入排序*endl;cout随机产生数据:endl;rand_sort(a);display(a);cout排序之后的数据endl;Binsertsort(a);display(a);coutendl;cout * 3.冒泡排序*endl;cout随机产生数据:endl;rand_sort(a);display(a);cout排序之后的数据endl;bubble_sort(a);display(a);coutendl;cout * 4.快速排序*endl;cout随机产生数据:endl;rand_sort(a);display(a);cout排序之后的数据endl;quick_sort(a, 0 ,len-1);display(a);coutendl;cout * 5.选择排序*endl;cout随机产生数据:endl;rand_sort(a);display(a);cout排序之后的函数endl;select_sort(a);display(a);coutendl;cout * 6.归并排序*endl;cout随机产生数据:endl;rand_sort(a);display(a);cout排序之后的数据endl;merge_sort(a , 0 , len);display(a);coutendl;cout * 7.堆排序*endl;cout随机产生数据:endl;rand_sort(a);display(a);cout排序之后的数据endl;head_sort(a );display(a);coutendl;cout * 8.希尔排序*endl;cout随机产生数据:endl;rand_sort(a);display(a);cout排序之后的数据endl;shell_sort(a);display(a);coutendl;cout * 9.基数排序*endl;cout随机产生数据:endl;rand_sort(a);display(a);cout排序之后的数据endl;dadix_sort(a);display(a);coutendl;return 0;void insertsort(int *a )int temp;for (int i = 1 ; i ai)temp = ai;ai = ai-1;for (int j = i - 1 ; temp aj ; -j )aj+1 = aj;aj+1 = temp;void Binsertsort(int *a ) /折半插入排序函数int temp;int low,high,mid;for (int i = 1 ; i len ; +i )temp = ai;low = 0 ; high = i- 1 ;while (low = high)mid = (low + high ) / 2 ;if ( temp high ; -j )aj+1 = aj;aj+1 = temp ;void bubble_sort(int *a) /冒泡排序int temp;for (int i = 1 ; i len ; +i )for (int j = 0 ; j aj+1 )temp = aj;aj = aj+1;aj+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 ( alow = ahigh & low high )-high;temp = alow;alow = ahigh;ahigh = temp ;while (alow = ahigh & low = 0 ; -j,-t )n = max_select_sort(a , t);if (j != n )temp = an;an = aj;aj = temp ;int max_select_sort(int *a, int t)/选择最大数int temp = a0;int flag = 0 ;for (int i = 0 ; i temp )temp = ai;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 inthigh - low;while(i = mid & j = high)if (ai = aj)br = ai;+r ; +i;elsebr = aj;+j;+r;while (i = mid )br = ai;+r;+i ;while (j = high)br = aj;+j;+r ;for (i = low ,j = 0 ; i = 0 ; -i )head_adgust(a , i , len);for ( i = len - 1 ; i = 0 ; -i )temp = a0;a0 = ai;ai = 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 (ai ai)break;elsetemp = alow;alow = ai;ai = temp;low = i ;void shell_insert(int *a , int dk) 希尔插入函数int temp;for (int i = dk ; i len ; +i )if (ai = 0 & temp aj ; j = j-dk )aj+dk = aj;aj+dk = temp