CC++实现的各种排序

/* 直插排序 */ void InsertSort(vector<int> &arr){ for(int i = 1;i < arr.size();++i){ for(int j = i;j > 0;--j){ if(arr[j] < arr[j - 1]){ int temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; } else break; } } } /* 冒泡排序 */ void BubbleSort1(vector<int> &arr){ for (int i = 0; i < arr.size() - 1; i++) { bool flag=true; for (int j = 0; j < arr.size() - i - 1; j++) { //经过第1趟可以找出最大的数 if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; flag=false; } } if(flag) return; } } void BubbleSort2(vector<int> &arr){ for (int i = 0; i < arr.size() - 1; i++) { bool flag=true; for (int j = arr.size()-1; j > i; j--) { if (arr[j] < arr[j - 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; flag=false; } } if(flag) return; } } /* 快速排序 */ void quicksort(vector<int> &arr, int left, int right) { if(left >= right) return ; int i = left; int j = right; int key = arr[left]; //比较的是第一个数 while(i < j) { while(i < j && key <= a[j]) { j--; } arr[i] = arr[j]; while(i < j && key >= a[i]) { i++; } arr[j] = arr[i]; } arr[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/ quicksort(arr, left, i - 1); quicksort(arr, i + 1, right); } /* 归并排序 */ //归并排序(递归) void Merge(int* a, int* b, int start, int end) { if (start >= end) return; int mid = (start + end) >> 1; //分成两部分 int start1 = start,end1 = mid; int start2 = mid + 1, end2 = end; //合并 Merge(a, b, start1, end1); Merge(a, b, start2, end2); int k = start; //进行比较 while (start1 <= end1 && start2 <= end2) b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++]; //当一方比较完 while (start1 <= end1) { b[k++] = a[start1++]; } while (start2 <= end2) { b[k++] = a[start2++]; } //将临时的数组拷贝到原来数组 for (k = start;k <= end;k++) a[k] = b[k]; } void MergeSort(int *a,int *b,int len) { Merge(a, b, 0, len - 1); } /**************************************/ //希尔排序 速度很难定量 但是效率挺高的 不稳定的算法 void Shellsort(int a[], int len){ int gap=len-1; //初始增量 bool flag=0; while(gap>=1){ if(gap==1) flag=1; for(int i=0;i<len;i++){ if(i+gap<len){ if(a[i]>a[i+gap]){ int temp=a[i]; a[i]=a[i+gap]; a[i+gap]=temp; } } else break; } gap=gap/3+1; //增量计算公式 if(flag) break; } } //堆排序 void HeapSort(int arr[],int len){ int i; //初始化堆，从最后一个父节点开始 for(i = len/2 - 1; i >= 0; --i){ Heapify(arr,i,len); } //从堆中的取出最大的元素再调整堆 for(i = len - 1;i > 0;--i){ int temp = arr[i]; arr[i] = arr[0]; arr[0] = temp; //调整成堆 Heapify(arr,0,i); } } //再看 调整成堆的函数 void Heapify(int arr[], int first, int end){ int father = first; int son = father * 2 + 1; while(son < end){ if(son + 1 < end && arr[son] < arr[son+1]) ++son; //如果父节点大于子节点则表示调整完毕 if(arr[father] > arr[son]) break; else { //不然就交换父节点和子节点的元素 int temp = arr[father]; arr[father] = arr[son]; arr[son] = temp; //父和子节点变成下一个要比较的位置 father = son; son = 2 * father + 1; } } }