C++实现快速排序,归并排序,堆排序

回忆几个重要的排序算法，留存：

#include <iostream>

*归并排序

using namespace std; /* 归并排序 @dragonboss */ int buff1[10] = {0}; int buff2[10] = {0}; void Merge(int arr[],int s1,int len1,int s2,int len2){ //拷贝数据缓存 for(int i = 0;i < len1;i++){ buff1[i] = arr[s1+i]; } for(int i = 0;i < len2;i++){ buff2[i] = arr[s2+i]; } int i=0,c1=0,c2=0; while(i < len1+len2){ if(buff1[c1] < buff2[c2] && c1 < len1){ arr[s1+i++] = buff1[c1++]; } else if(c2 < len2){ arr[s1+i++] = buff2[c2++]; } else{ break; } } while(c1 < len1){ arr[s1+i++] = buff1[c1++]; } while(c2 < len2){ arr[s1+i++] = buff2[c2++]; } } void Merge_Sort(int arr[],int first,int last){ int mid = (first + last)/2; if(first == last) return; Merge_Sort(arr,first,mid); Merge_Sort(arr,mid+1,last); Merge(arr,first,mid-first+1,mid+1,last -mid); }

*快排

/* 快速排序 @dragonboss */ void Quick_Sort(int arr[],int start,int last){ int point = arr[start]; int i = start; int j = last; while(i < j){ //循环找到比枢纽元小的，这样就可以将这个值存储到前排的位置 while(i < j && arr[j] >= point) j--; //找到了比枢纽元小的，存储到前排 arr[i] = arr[j]; //前排循环查找比枢纽元大的元素 while(i < j && arr[i] <= point) i++; //找到了比枢纽元大的元素了，存储到后排空出的位置 arr[j] = arr[i]; } //上循环执行的结果总会留一个空位，最后一个空位就是两个游标相等的位置。 arr[i] = point; if(start < i-1)Quick_Sort(arr,start,i-1); if(i+1< last)Quick_Sort(arr,i+1,last); }

*堆排

void BuildeHeap(int arr[],int len){ int temp = 0; for(int i = len-1;i > 0;i--){ if(arr[i] < arr[(i-1)/2]){ temp = arr[i]; arr[i] = arr[(i-1)/2]; arr[(i-1)/2] = temp; } } } void HeapSort(int arr[],int len){ int temp = 0; BuildeHeap(arr,len); for(int i = 1;i < len;i++){ temp = arr[0]; arr[0] = arr[len-i]; arr[len-i] = temp; BuildeHeap(arr,len-i); } }

*测试：

int main(){ /* int arr[] = {2,13,34,4,6,4,22,44,4}; // int *a = arr; Quick_Sort(arr,0,8); for(int i =0;i<9;i++){ cout << arr[i] << endl; }*/ int a[] = {21,134,34,4,5556,74,22,44,94}; HeapSort(a,9); //Merge_Sort(a,0,8); for(int i =0;i<9;i++){ cout << a[i] << endl; } return 0; }