快速排序算法(Quicksort)

一、排序算法（Sorting algorithm）是计算机科学最古老、最基本的课题之一。要想成为合格的程序员，就必须理解和掌握各种排序算法。目前，最常见的排序算法大概有七八种，其中”快速排序”（Quicksort）使用得最广泛，速度也较快。它是图灵奖得主C. A. R. Hoare（1934–）于1960时提出来的。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
（1） 分治法的基本思想
将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

（2）快速排序的基本思想，整个排序过程只需要三步

• 在数据集之中，选择一个元素作为”基准”（pivot）。
• 所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。
• 对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

二、快速排序算法实现：

JavaScript：

function QuickSort(arr, left, rigth) {
    var i = left;
    var j = rigth;
    var povit = Math.floor((left + rigth) / 2);
    var con = arr[povit];
    while (i <= j) {
        while (arr[i] < con) { i++; } while (arr[j] > con) {
            j--;
        }
        if (i <= j) {
            var tmp = arr[i];
            arr[i] = arr[j];
            i++;
            arr[j] = tmp;
            j--;
        }
    }
    if (left < j) {
        QuickSort(arr, left, j);
    }
    if (i < rigth) {
        QuickSort(arr, i, rigth);
    }
}
var arr = [10, 1, 5, 9, 3, 6, 2, 4, 8, 7, 15, 11, 13, 14, 12, 0, 20, 18, 16, 17, 19];
QuickSort(arr, 0, arr.length - 1);
alert(arr);

C# 实现快速排序算法 :

static void QuickSort(ref List < int > nums, int left, int right) 
{
	if (left < right) 
	{
		int i = left;
		int j = right - 1;
		int middle = nums[(left + right) / 2];
		while (true) 
		{
			while (i < right && nums[i] < middle) { i++; } ; while (j > 0 && nums[j] > middle) 
			{
				j--;
			}
			;
			if (i == j) break;
			nums[i] = nums[i] + nums[j];
			nums[j] = nums[i] - nums[j];
			nums[i] = nums[i] - nums[j];
			if (nums[i] == nums[j]) j--;
		}
		QuickSort(ref nums, left, i);
		QuickSort(ref nums, i + 1, right);
	}
}

转载请注明：清风亦平凡 » 快速排序算法(Quicksort)

喜欢 (1)or分享 (0)

赏 支付宝扫码打赏 微信打赏