云南龙网

  1. 首页 > 云知道 > >

合并排序实验报告总结 合并排序c语言算法代码( 四 )

云知道合并

{ //最后一个有孩子的节点的位置 i= (length -1) / 2 for (int i = (length -1) / 2 ; i >= 0; --i) HeapAdjust(H,i,length);}/** * 堆排序算法 */void HeapSort(int H[],int length){ //初始堆 BuildingHeap(H, length); //从最后一个元素开始对序列进行调整 for (int i = length - 1; i > 0; --i) { //交换堆顶元素H[0]和堆中最后一个元素 int temp = H[i]; H[i] = H[0]; H[0] = temp; //每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整 HeapAdjust(H,0,i); }}
int main{ int H[10] = {3,1,5,7,2,4,9,6,10,8}; cout<<"初始值："; print(H,10); HeapSort(H,10); //selectSort(a, 8); cout<<"结果："; print(H,10);
}五、冒泡排序（Bubble Sort）
算法思想：
冒泡遍历所有的数据，每次对相邻元素进行两两比较，如果顺序和预先规定的顺序不一致，则进行位置交换；这样一次遍历会将最大或最小的数据上浮到顶端，之后再重复同样的操作，直到所有的数据有序 。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端 。
算法代码：

void bubbleSort(int a[], int n){ for(int i =0 ; i< n-1;i) { for(int j = 0; j < n-i-1;j) { if(a[j] > a[j 1]) { int tmp = a[j] ; a[j] = a[j 1] ; a[j 1] = tmp; } } }}六、快速排序（Quick Sort）
算法思想：
快速排序是由东尼·霍尔所发展的一种排序算法 。在平均状况下，排序 n 个项目要Ο(n logn)次比较 。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见 。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists） 。
算法步骤：

  1. 从数列中挑出一个元素，称为 “基准”（pivot） 。
  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边） 。在这个分区退出之后，该基准就处于数列的中间位置 。这个称为分区（partition）操作 。
  3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序 。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了 。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去 。
算法代码：
void print(int a[], int n){ for(int j= 0; j cout< } cout<}
void swap(int *a, int *b){ int tmp = *a; *a = *b; *b = tmp;}
int partition(int a[], int low, int high){ int privotKey = a[low]; //基准元素 while(low < high){ //从表的两端交替地向中间扫描 while(low < high && a[high] >= privotKey) --high; //从high 所指位置向前搜索，至多到low 1 位置 。将比基准元素小的交换到低端 swap(&a[low], &a[high]); while(low < high && a[low] <= privotKey )low; swap(&a[low], &a[high]); } print(a,10); return low;}

推荐阅读


上一篇：详解proteus仿真步骤 keil5仿真调试教程

下一篇：天将雄狮什么日的人,《天将雄师》评测