发布时间 : 星期六 文章南邮数据结构上机实验四内排序算法的实现以及性能比较更新完毕开始阅读9883f069f9c75fbfc77da26925c52cc58ad69076
.
列不断增长直到全部排序完毕。
2) 直接插入排序：
插入排序的思想是将一组无序的元素分别插入一个已经有序的的数组里，并保证插入后的数组也是有序的。当所有无序组的元素都插入完毕时，一个有序数组构造完成。数组n[1…r]为初始的一个无序数组（为了直观起见，我们这里设定数组从1开始，而不是0），则n[1]默认为只有一个元素的有序数组，n[2]插入只有n[1]构成的有序数组中，则此时有序数组的元素数量变为2。以此类推，到第i个元素时，前i-1个元素已经是有序的，此时只需将第i个元素插入到有序数组中并使之保持有序。如此直至最后一个元素插入完毕，整个插入排序完成。 3) 冒泡排序：
冒泡排序每遍历一次数组，便将最大的元素放到数组最后边。下次遍历将次大的元素放到数组倒数第二位，依次类推，直至将最小的元素放到最前边，此时冒泡排序完成。 4) 快速排序：
快速排序是采用了分而治之的思想，但与合并排序有所不同的是快速排序先“工作”（这里是分割或partition），再递归。快速排序的主要思想是保证数组前半部分小于后半部分的元素，然后分别对前半部分和后半部分再分别进行排序，直至所有元素有序。 5) 两路合并排序
两路合并排序算法的基本思想是：将待排序元素平分成大小大致相同的两个子序列，然后对每个子序列分别使用递归的方法进行两路合并排序，直到子序列长度变为1，最后利用合并算法将得到的已排序好的两个子序列合并成一个有序的序列。 两路合并排序算法的核心部分是将子问题的解组合成原问题解得合并操作。常用的操作是新建一个序列，序列的大小等于要合并的两个子序列的长度之和。比较两个子序列中的最小值，输出其中较小者到新建的序列中，重复此过程直到其中一个子序列为空。如果另一个子序列中还有元素未输出，则将剩余元素依次输出到新建序列中即可。最终得到一个有序序列。
此外还对快速排序进行了改进，改进算法流程图如下所示：
.
.
GQuickSort ()
四、程序代码
template
void GQuickSort(T A[],int n) //改进的快速排序 {
GQSort(A,0,n-1); }
template
void GQSort(T A[],int left,int right) {
int i,j;
.
.
}
if(right>=9) {
if(left i=left; j=right+1; do { do i++;while (A[i] Swap(A[i],A[j]); }while(i Swap(A[left],A[j]); QSort(A,left,j-1); QSort(A,j+1,right); } } else { InsertSort(A,right-left+1); return ; } 五、测试和调试 1. 测试用例和结果 测试结果如下图 1) 生成随机数据 2) 简单选择排序及其所需时间 . . 3)4). 直接插入排序及其所需时间 冒泡排序及其所需时间