算法笔记 之 快速排序的几种写法

这是基本都一样的部分。

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： 从两边向中间，不符合要求就交换。

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不变）。

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始终保存着基准值，即空出来一个位置，可以原地排序。）

这个是我认为相对前两种较好的！因为不会太多的交换操作。

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版的，其实很简单，就是取一个随机数。

    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);
    }