排序算法

直接插入排序： 整个序列分为有序区和无序区，取第一个元素作为初始有序区，然后第二个开始，依次插入到有序区的合适位置，直到排好序。第一个for循环对从第二个开始的所有的数字遍历，嵌套的for循环是每次遍历数字时都取无序区的一个元素与有序区的元素比较，如果比有序区的要小则交换，直到合适的位置。

void InsertSort2(vector<int> &num) { for(int i = 1;i < num.size();++i) { for(int j = i;j > 0;--j) { if(num[j] < num[j - 1]) { int temp = num[j]; num[j] = num[j-1]; num[j-1] = temp; } } } }

冒泡排序 第一个for循环是遍历所有元素，第二个for循环是每次遍历元素时都对无序区的相邻两个元素进行一次比较，若反序则交换.

时间复杂度最坏的情况是反序序列，要比较n(n-1)/2次，时间复杂度为O(n^2 )，最好的情况是正序，只进行(n-1)次比较，不需要移动，时间复杂度为O(n)，而平均的时间复杂度为O(n^2 )

void BubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { int count = 0; for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { count++; int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } if(count == 0) { break; } } }

快速排序 快速排序首先选一个轴值(pivot，也有叫基准的)，将待排序记录划分成独立的两部分，左侧的元素均小于轴值，右侧的元素均大于或等于轴值，然后对这两部分再重复，直到整个序列有序。

void OnceSort(int arr[], int first, int end) { int i = first,j = end;//当i<j即移动的点还没到中间时循环 while(i < j)//右开始，保证i<j并且arr[i]<=arr[j]的时候就向左遍历 { //这时候已经跳出循环，说明j>i 或者 arr[i]大于arr[j]了，如果i<j那 就是arr[i]大于arr[j]，那就交换 while(i < j && arr[i] <= arr[j]) --j; if(i < j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } //对另一边执行同样的操作 while(i < j && arr[i] <= arr[j]) ++i; if(i < j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } //返回已经移动的一边当做下次排序的轴值 return i; } QuickSort(int arr[], int first, int end) { int pivot = OnceSort(arr,first,end); //已经有轴值了，再对轴值左右进行递归 QuickSort(arr,first,pivot-1); QuickSort(arr,pivot+1,end); }

堆排序 堆的结构类似于完全二叉树，每个结点的值都小于或者等于其左右孩子结点的值，或者每个节点的值都大于或等于其左右孩子的值。堆排序过程将待排序的序列构造成一个堆，选出堆中最大的移走，再把剩余的元素调整成堆，找出最大的再移走，重复直至有序。

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; } } } 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 Merge(int arr[], int reg[], int start, int end) { if (start >= end)return; int len = end - start, mid = (len >> 1) + start; //分成两部分 int start1 = start, end1 = mid; int start2 = mid + 1, end2 = end; //然后合并 Merge(arr, reg, start1, end1); Merge(arr, reg, start2, end2); int k = start; //两个序列一一比较,哪的序列的元素小就放进reg序列里面,然后位置+1再与另一个序列原来位置的元素比较 //如此反复,可以把两个有序的序列合并成一个有序的序列 while (start1 <= end1 && start2 <= end2) reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++]; //然后这里是分情况,如果arr2序列的已经全部都放进reg序列了然后跳出了循环 //那就表示arr序列还有更大的元素(一个或多个)没有放进reg序列,所以这一步就是接着放 while (start1 <= end1) reg[k++] = arr[start1++]; //这一步和上面一样 while (start2 <= end2) reg[k++] = arr[start2++]; //把已经有序的reg序列放回arr序列中 for (k = start; k <= end; k++) arr[k] = reg[k]; } void MergeSort(int arr[], const int len) { //创建一个同样长度的序列,用于临时存放 int reg[len]; Merge(arr, reg, 0, len - 1); }