【排序】快速排序代码-C语言版

墨蓝 2022-06-14 00:56 188阅读 0赞

# 排序代码 #

#include <stdio.h>
    #include <stdlib.h>
    
    // increase sort
    int partition(int arr[], int low, int high)
    {
    	int pivot = (low+high)/2;
    	int pivot_key = arr[(low+high)/2];
    	arr[pivot] = arr[low];
    	while (low < high) {
    		while ( (arr[high] > pivot_key) && (low < high) ) {
    			high--;
    		}
    		if ( low < high ) 
    			arr[low++] = arr[high];
    		while ( (arr[low] < pivot_key) && (low < high) ) {
    			low++;
    		}
    		if ( low < high )
    			arr[high--] = arr[low];
    	}
    	arr[low] = pivot_key;
    	return low;
    }
    
    void qsort(int arr[], int low, int high)
    {
    	int pivot = partition(arr, low, high);
    	if (pivot > low) 
    		qsort(arr, low, pivot-1);
    	if (high > pivot)
    		qsort(arr, pivot+1, high);
    }
    
    void qsort(int arr[], int len)
    {
    	qsort(arr, 0, len-1);
    }

# 测试代码 #

void print_arr(int arr[], int len)
    {
    	for (int i=0; i<len; ++i) {
    		printf ("%3d ", arr[i]);
    	}	
    	printf("\n");
    }
    
    void qsort_test(int arr[], int len)
    {
    	printf("before sort :");
    	print_arr(arr, len);
    	printf("after sort  :");
    	qsort(arr, len);
    	print_arr(arr, len);
    	printf("******************************************\n");
    }
    
    void test_qort_func()
    {
    	// 有点挫...简单测一下~~~ 有时间再改改  
    	int arr1[] = {1};
    	int arr2[] = {1,2,3};
    	int arr3[] = {3,2,1};
    	int arr4[] = {1,2,2,1,4,5};
    	int arr5[] = {7,5,9,20,13,108,3,7,1,-4,28};
    	qsort_test( arr1, sizeof(arr1)/sizeof(int));
    	qsort_test( arr2, sizeof(arr2)/sizeof(int));
    	qsort_test( arr3, sizeof(arr3)/sizeof(int));
    	qsort_test( arr4, sizeof(arr4)/sizeof(int));
    	qsort_test( arr5, sizeof(arr5)/sizeof(int));
    }
    
    int main(int argc, char* argv[])
    {
    	test_qort_func();
    	return 0;
    }

# PS： #

简单补充一下：

大家都理解快排的思路就是选一个pivot，然后遍历，把小于pivot的放到前面，大于pivot的放到后面。但是这个思路转换成代码怎么实现？本文也是参照教科书，给出一个相对比较高效的实现方式。即(以升序为例)：

1、左右交替检索，先从左边检索，如比pivot小则继续，否则跳到最右边继续反向检索；

2、从右边检索时，如果某个值大于pivot，则继续，否则说明这个需要被交换到左侧。则将它与左边检索停止处的值交换

3、检索时，把pivot的值保存到一个临时变量，这样数组中就空出来一个“坑”，当需要交换时，直接把值填到这个“坑”里。然后又空出来一个新的坑，供下次交换使用；

4、注意递归的实现方式。