首页 > 代码库 > 快排、归并排序(分治)、堆排序
快排、归并排序(分治)、堆排序
一、快速排序
1)算法简介
快速排序是由C. A. R. Hoare所发展的一种排序算法。其基本思想是基本思想是,通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
2)算法描述
快速排序使用分治法来把一个串(list)分为两个子串行(sub-lists)。
步骤为:
1、从数列中挑出一个元素,称为 "基准"(pivot),
2、重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
3、递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
最差时间复杂度:O(n^2)
最优时间复杂度:O(n log n)
平均时间复杂度:O(n log n)
最差空间复杂度:根据实现的方式不同而不同
3)算法代码
快速排序有很多版本,但关键是划分的思想。
void QuickSort(int L[], int l, int r) { int i, j, pivot; if(l >= r) return; //std::swap(L[l], L[(l+r)/2]);//以中间的数作为基准数的 //int p = l + rand() % (r - l + 1); //rand_partition() //std::swap(L[l], L[p]); i = l, j=r, pivot = L[l]; while(i < j) { while(i < j && L[j] >= pivot)//从右向左找第一个比key小的数 j--; if(i < j) L[i++] = L[j]; while(i < j && L[i] <= pivot)//从左向右找第一个比key大的数 i++; if(i < j) L[j--] = L[i]; } L[i] = pivot; QuickSort(L, l, i-1); QuickSort(L, i+1, r); }
void qsort1(int L[], int l, int r) { if (l >= r) return; int i = l, j; for (j = l + 1; j <= r; j++) /* invariant: L[l+1..i] < L[l] && L[i+1..j-1] >= L[l]*/ if (L[j] < L[l]) //< std::swap(L[++i], L[j]); std::swap(L[l], L[i]); /* L[l..i-1] < L[i] <= L[i+1..r]*/ qsort1(L, l, i - 1); qsort1(L, i + 1, r); }
void qsort3(int L[], int l, int r) { if (l >= r) return; int pivot = L[l]; int i = l, j = r + 1; while(i <= j) { do { i++; } while (i <= r && L[i] < pivot); do { j--; } while (L[j] > pivot); if (i > j) break; std::swap(L[i], L[j]); } std::swap(L[l], L[j]); qsort3(L, l, j - 1); qsort3(L, j + 1, r); }
void qsort4(int L[], int l, int r) { if (l >= r) return; int pivot = L[l]; int i = l - 1, j = r + 1; while(i <= j) { do { i++; } while (/*i <= r &&*/ L[i] < pivot); do { j--; } while (L[j] > pivot); if (i > j) break; std::swap(L[i], L[j]); } //print(L, l, r);putchar('\n'); std::swap(L[l], L[j]); qsort3(L, l, j - 1); qsort3(L, j + 1, r); }
4)利用快排划分细思想求数组第k小的数,或者最小的前k个数
(1)第k小的数
//一次划分后,主元左边的数都小于主元,主元右边的数都大于或者等于主元 int Rand_Partition(int A[], int l, int r) { int i, j, pivot; int p = l + rand()% (r - l + 1); std::swap(A[l], A[p]); pivot = A[l], i = l, j = r; while(i < j) { while(i < j && A[j] >= pivot) //从右向左找第一个小于pivot的数 j--; if(i < j) A[i++] = A[j]; while(i < j && A[i] < pivot) //从左向右找第一个大于或等于pivot的数 i++; if(i < j) A[j--] = A[i]; } A[i] = pivot; return i; } int Rand_Select(int A[], int l, int r, int i) //ith big in A[l, ..., r] { int pivotloc, k; if(l == r) return A[l]; pivotloc = Rand_Partition(A, l, r); k = pivotloc - l + 1; if(i == k) return A[pivotloc]; else if(i < k) return Rand_Select(A, l, pivotloc-1, i); else return Rand_Select(A, pivotloc+1, r, i-k); }
void GetleastNumber(int input[], int n, int output[], int k) { if (n <= 0 || k <= 0 || k > n) return; int l = 0, r = n - 1; int pivotloc = Partition(input, l, r); //l..|....|.....|...r // p < k-1 <= p while (pivotloc != k - 1) { if (pivotloc < k - 1) pivotloc = Partition(input, pivotloc + 1, r); else pivotloc = Partition(input, l, pivotloc - 1); } memcpy(output, input, k * sizeof(int)); }
二、归并排序
1)算法简介
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。归并排序是一种稳定的排序方法。
将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。
2)算法描述
归并排序具体算法描述如下(递归版本):
1、Divide: 把长度为n的输入序列分成两个长度为n/2的子序列。
2、Conquer: 对这两个子序列分别采用归并排序。
3、Combine: 将两个排序好的子序列合并成一个最终的排序序列。
归并排序的效率是比较高的,设数列长为N,将数列分开成小数列一共要logN步,每步都是一个合并有序数列的过程,时间复杂度可以记为O(N),故一共为O(N*logN)。因为归并排序每次都是在相邻的数据中进行操作,所以归并排序在O(N*logN)的几种排序方法(快速排序,归并排序,希尔排序,堆排序)也是效率比较高的。
3)算法代码
//将两个有序的数组a[first,...,mid], a[mid+1,...,last]合并成一个有序的(借助temp数组) void MergeTwoSortedArray(int a[], int first, int mid, int last, int temp[]) { int i = first, j = mid + 1; int k = 0; while ( i <= mid && j <= last) if (a[i] < a[j]) temp[k++] = a[i++]; else temp[k++] = a[j++]; while (i <= mid) temp[k++] = a[i++]; while (j <= last) temp[k++] = a[j++]; //for (i = 0; i < k; i++) // a[first + i] = temp[i]; memcpy(a + first, temp, sizeof(int) * (last - first + 1)); } //递归地对a[first,...,last]区间的元素二分排序再合并 void MergeSortR(int a[], int first, int last, int temp[]) { if (first < last) { int mid = (first + last) / 2; //将a[first, last]平分为a[first,...,mid]和a[mid+1,...,last] MergeSortR(a, first, mid, temp); //左边有序:递归地将a[first,...,mid]归并为有序的temp[first,...,mid] MergeSortR(a, mid + 1, last, temp); //右边有序:递归地将a[mid+1,...,last]归并为有序的temp[mid+1,...,last] MergeTwoSortedArray(a, first, mid, last, temp); //合并后全部有序:将有序的temp[first,...,mid]和有序的temp[mid+1,...,last]归并到a[first, last] } } void MergeSort(int a[], int n) { int *temp = new int[n]; //临时数组 if (temp == NULL) return; memset(temp, 0, sizeof(int)*n); MergeSortR(a, 0, n - 1, temp); delete []temp; }(2)如果每次在归并函数内部分配临时的数组空间,归并函数的写法也可以有几种:
//先将左右有序序列拷贝到临时数组后再直接归并到原数组 void MergeTwoSortedArray1(int a[], int first, int mid, int last) { int i, j; int n1 = mid - first + 1; int n2 = last - mid; int *L = new int[n1]; //临时数组 int *R = new int[n2]; //for (i = 0; i < n1; i++) //左边有序序列 // L[i] = a[first + i]; //for (j = 0; j < n2; j++) // R[j] = a[mid + 1 + j]; //右边有序序列 for (i = first; i <= mid; i++) L[i - first] = a[i]; for (j = mid + 1; j <= last; j++) R[j - mid - 1] = a[j]; i = 0, j = 0; int k = first; while (i < n1 && j < n2) { if (L[i] < R[j]) a[k++] = L[i++]; else a[k++] = R[j++]; } while (i < n1) a[k++] = L[i++]; while (j < n2) a[k++] = R[j++]; delete []L; delete []R; }
//先将左右有序序列拷贝到临时数组后再直接归并到原数组(使用哨兵) void MergeTwoSortedArray2(int a[], int first, int mid, int last) { int i, j; int n1 = mid - first + 1; int n2 = last - mid; int *L = new int[n1 + 1]; //临时数组,末尾为哨兵元素 int *R = new int[n2 + 1]; //for (i = 0; i < n1; i++) //左边有序序列 // L[i] = a[first + i]; //for (j = 0; j < n2; j++) // R[j] = a[mid + 1 + j]; //右边有序序列 //L[i] = INT_MAX, R[j] = INT_MAX; //末尾添加哨兵元素 for (i = first; i <= mid; i++) L[i - first] = a[i]; for (j = mid + 1; j <= last; j++) R[j - mid - 1] = a[j]; L[i - first] = INT_MAX, R[j - mid - 1] = INT_MAX; i = 0, j = 0; for (int k = first; k <= last; k++) { if (L[i] < R[j]) a[k] = L[i++]; else a[k] = R[j++]; } delete []L; delete []R; }
void MergeSortR1(int a[], int first, int last) { if (first < last) { int mid = (first + last) / 2; MergeSortR1(a, first, mid); MergeSortR1(a, mid + 1, last); MergeTwoSortedArray3(a, first, mid, last); } } void MergeSort1(int a[], int n) { MergeSortR1(a, 0, n - 1); }
4)求逆序对
利用归并排序的思想可以实现求逆序数对
int Merge(int a[], int first, int mid, int last, int temp[]) { int inversion = 0; int i = first, j = mid + 1, k = 0; while (i <= mid && j <= last) { if (a[i] <= a[j]) { temp[k++] = a[i++]; }else //a[i] > a[j],而a[first,..,i,..,mid]递增有序,因此a[i~mid]与a[j]构成逆序对,共mid-i+1个 { temp[k++] = a[j++]; inversion += mid - i + 1; } } while (i <= mid) temp[k++] = a[i++]; while (j <= last) temp[k++] = a[j++]; memcpy(a + first, temp, sizeof(int) * (last - first + 1)); return inversion; } int MergeInversionR(int a[], int first, int last, int temp[]) { int inversion = 0; if (first < last) { int mid = (first + last) >> 1; inversion += MergeInversionR(a, first, mid, temp); //找左半段的逆序对数目 inversion += MergeInversionR(a, mid + 1, last, temp);//找右半段的逆序对数目 inversion += Merge(a, first, mid, last, temp); //在找完左右半段逆序对以后两段数组有序,然后找两段之间的逆序对。最小的逆序段只有一个元素。 } return inversion; } int MergeInversion(int a[], int n) { int inversion = 0; int *temp = new int[n]; memset(temp, 0, sizeof(int)*n); inversion = MergeInversionR(a, 0, n - 1, temp); delete []temp; return inversion; }
三、堆排序
见 利用堆实现堆排序&优先队列。