算法笔记 之 快速排序的几种写法
这是基本都一样的部分。[cpp]
void print_arr(int *arr, int n) {
int i;
for (i = 0; i < n; i++) {
if (!i) {
printf("%d", arr[i]);
} else {
printf(" %d", arr[i]);
}
}
printf("\n");
}
void sort(int * arr, int start, int end){
if(end < start)
return;
int index = quik_sort(arr, start, end);
sort(arr, start, index-1);
sort(arr,index +1,end);
}
int main() {
//cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
int n = 6;
int max = 10;
int * arr = (int *) malloc(sizeof(int) * n);
srand(time(0));
//cout << time(0) << endl;
for (int i = 0; i < n; i++) {
arr[i] = rand() % max;
}
print_arr(arr, n);
sort(arr, 0, n-1);
print_arr(arr, n);
return 0;
}
先说非随机化算法：
方法1： 从两边向中间，不符合要求就交换。
[cpp]
int quik_sort(int * arr, int start, int end) {
int i = start;
int j = end + 1;
int x = arr[start];
while(true){
//这里是 "++i"
while(arr[++i] < x);//从后向前找到第一个比 基准（x）小的数。 i指向该数
//--j 所以要在前面 j=end+1
while(arr[--j] > x);//从前到后 第一个比 基准（x）大的数。 j指向该数
if(i >= j)
break;
//进行交换操作
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
arr[start] = arr[j];
arr[j] = x;
//print_arr(arr, 6);
//cout << start << " - " << end << " j=" << j << endl;
return j;
}
方法2：
第一次交换：swap(arr,index,end); 是交换最后一个值和最后一个值。（遍历树从start -> end-1），也可以说是让arr[end]暂存基准值，循环结束后在交换过来。
第二次交换：swap(arr,index++,i); 保证较小的值在前面
地三次交换：swap(arr, end, index); 当期循环结束的时候，index指向的中间的某个位置（值的是基准值应该在的位置），此时arr[index] 是大于或等于基准值的，可以和arr[end]（基准值进行交换）
这个算法可以从前向后遍历，也可以从后向前遍历。
index指向的数可以理解为一个待与后面比基准（pivot）交换的数（i指向的数始终比pivot小，要交换到前面），可以比pivot小（就是index==i,就和自身交换，index++）或大（不交换，index不变）。
[cpp]
int quik_sort(int * arr, int start, int end) {
int index = start;
int pivot = arr[index];
swap(arr,index,end);
for(int i=start; i<end ; i++){
if(arr[i] < pivot){
swap(arr,index++,i);
}
}
swap(arr, end, index);
return index;
}
方法3：只有一个quick_sort方法，递归调用自身。其实也就是从两边向中间靠拢。
但是这里每次不是进行两个值的交换，而是把一个值赋值给另一个。 （key始终保存着基准值，即空出来一个位置，可以原地排序。）
这个是我认为相对前两种较好的！因为不会太多的交换操作。
[cpp]
void quick_sort(int * arr, int start, int end){
if(end < start)
return;
int i,j,key;
i = start;
j = end;
key = arr[i];
while(i < j){
while (i < j && arr[j] > key)
j--;
if (i < j)
arr[i++] = arr[j];
while (i < j && arr[i] < key)
i++;
if (i < j)
arr[j--] = arr[i];
}
arr[i] = key;
if(start < i-1)
quick_sort(arr, start, i-1);
if(end > i+1)
quick_sort(arr, i+1, end);
}
随机化算法：
随机化的好处就是防止出现最坏的情况。
Java版的，其实很简单，就是取一个随机数。
[java] www.zzzyk.com
private static <E> int partition(E[] array, int begin, int end, Comparator<? super E> cmp) {
int index = begin + RND.nextInt(end - begin + 1);
E pivot = array[index];
swap(array, index, end);
for (int i = index = begin; i < end; ++ i) {
if (cmp.compare(array[i], pivot) <= 0) {
swap(array, index++, i);
}
}
swap(array, index, end);
return (index);
}
补充：软件开发 , C++ ,
