算法导论 第7章 高速排序

gaohan

　　高速排序在最坏情况下的时间复杂度为O(n^2)，尽管在最坏情况下执行时间比較差，可是高速排序一般是用于排序的最佳选择。由于其平均性能相当好，期望的执行时间为O(nlgn)，且在O(nlgn)的记号中隐含的常数因子非常小。
　　


　　高速排序和合并排序有相似之处，都是须要划分序列，在合并排序中。划分的过程非常easy。直接选择元素序列的中间位划分位置，排序是在合并的过程中实现的，所以合并排序的合并过程非常重要。相比合并排序，高速排序就没有合并的过程。仅仅有划分，高速排序的划分过程非常重要，排序是在划分的过程中实现的。
　　


/*
*算法导论 第七章 高速排序
*最坏情况下时间复杂度为O(n^2)，这样的情况出如今每次选择pivot的时候
*都选到了最大或者最小的元素。即每次划分都有一边为空。　　
*其平均时间复杂度为O(nlgn)，仅仅要每次划分，每一边的元素都至少有一个即可
*/
#include <iostream>
#include <ctime>
using namespace std;
void printArray(int arr[], int len)
{
for (int i=0; i<len; i++)
{
cout << arr << &quot; &quot;;
}
cout << endl;
}
void quickSort(int arr[], int p, int r);
int partition(int arr[], int p, int r);
void exchange(int arr[], int i, int j);
int randomizedPartition(int *arr, int p, int r);
void randomizedQuickSort(int *arr, int p, int r);
int main()
{
int arr[] = {12, 21, 9, 80, 3, 11, 90, 4, 67};
int len = sizeof(arr) / sizeof(arr[0]);
cout << &quot;原数组：&quot; << endl;
printArray(arr, len);
//quickSort(arr, 0, len-1);
randomizedQuickSort(arr, 0, len-1);
cout << &quot;高速排序后的数组：&quot; << endl;
printArray(arr, len);
}
void quickSort(int arr[], int p, int r)
{
if (p < r)
{
int q = partition(arr, p, r);
quickSort(arr, p, q-1);
quickSort(arr, q+1, r);
}
}
int partition(int arr[], int p, int r)
{
int pivot = arr[r];
int i = p - 1;//i前面的（包含i）的元素都是不大于pivot的。i后面的都是大于pivot的元素
int j;//j后面的（包含j）都是还没有划分的
for (j=p; j<=r-1; j++)
{
if (arr[j] <= pivot)
{
i++;
exchange(arr, i, j);
}
}
i++;
exchange(arr, i, r);
return i;
}
void exchange(int arr[], int i, int j)
{
int temp = arr;
arr = arr[j];
arr[j] = temp;
}
/*
*随机化划分
*/
int randomizedPartition(int *arr, int p, int r)
{
srand(time(NULL));
int i = p + rand() % (r-p+1);
exchange(arr, i, r);
return partition(arr, p, r);
}
/*
*随机化高速排序
*期望时间复杂度为O(nlgn)
*/
void randomizedQuickSort(int *arr, int p, int r)
{
if (p < r)
{
int q = randomizedPartition(arr, p, r);
randomizedQuickSort(arr, p, q-1);
randomizedQuickSort(arr, q+1, r);
}
}




　　


　　习题7-6 对区间的模糊排序。算法思想见 http://blog.csdn.net/mishifangxiangdefeng/article/details/7681109，代码例如以下：
　　



/*
*算法导论 第七章 习题7-6
*算法思想跟高速排序相似，仅仅是对于区间的划分处理有点差别
*时间复杂度也为O(nlgn)，
*在全部区间都有重叠时，就仅仅会进行一次划分，时间复杂度为O(n)
*/
#include <iostream>
#include <ctime>
using namespace std;
typedef struct Interval
{
int a;//左端点
int b;//右端点
Interval(){}
Interval(int x, int y)
{
a = x;
b = y;
}
bool operator<(const Interval &interval)
{
return b < interval.a;
}
bool operator>(const Interval &interval)
{
return a > interval.b;
}
bool operator==(const Interval &interval)
{
return a<=interval.b && b>=interval.a;
}
}Interval;
void printArray(Interval arr[], int len)
{
for (int i=0; i<len; i++)
{
cout << &quot;[&quot; << arr.a << &quot;, &quot; << arr.b << &quot;]&quot; << &quot; &quot;;
}
cout << endl;
}
void quickSort(Interval arr[], int p, int r);
Interval partition(Interval arr[], int p, int r);
void exchange(Interval arr[], int i, int j);
int main()
{
cout << &quot;请输入区间个数：&quot; << endl;
int len;
cin >> len;
Interval *arr = new Interval[len];
srand(time(NULL));
for (int i=0; i<len; i++)
{
arr.a = rand() % 100;
arr.b = rand() % 100;
if (arr.a > arr.b)
{
int temp = arr.a;
arr.a = arr.b;
arr.b = temp;
}
}
cout << &quot;原区间数组：&quot; << endl;
printArray(arr, len);
quickSort(arr, 0, len-1);
cout << &quot;模糊排序后的区间数组：&quot; << endl;
printArray(arr, len);
return 0;
}

void quickSort(Interval arr[], int p, int r)
{
if (p < r)
{
Interval q = partition(arr, p, r);
if (q.a > p)
{
quickSort(arr, p, q.a);
}
if (q.b < r)
{
quickSort(arr, q.b, r);
}
}
}
Interval partition(Interval arr[], int p, int r)
{
Interval pivot = arr[r];
int i = p - 1;//i前面的（包含i）元素都是小于pivot的
int j = r + 1;//j后面的（包含j）的元素都是大于pivot的
int k = p;//i和k之间的元素师和pivot相等的，k和j之间的元素是还未比較的
Interval divider(i, j);
while (k<j & k<=r)
{
if (arr[k] < pivot)
{
i++;
exchange(arr, i, k);
k++;
} else if (arr[k] > pivot) {
j--;
exchange(arr, k, j);
} else {
/*
*假设相等，说明arr[k]和pivot的区间有重叠，则必须将枢纽点区间缩小，取arr[k]和pivot的重叠区间
*否则就不能保证划分的准确性
*比如区间[5, 9], [1, 7], [0, 3]，假设去pivot=[1, 7]。则[5, 9]和[0, 3]的顺序不会被交换。这是错误的
*必须每次遇到重叠区间，就更新pivot
*/
pivot.a = max(pivot.a, arr[k].a);
pivot.b = min(pivot.b, arr[k].b);
k++;
}
}
if (i > divider.a)
{
divider.a = i;
}
if (j < divider.b)
{
divider.b = j;
}
return divider;
}
void exchange(Interval arr[], int i, int j)
{
Interval temp = arr;
arr = arr[j];
arr[j] = temp;
}