在要求输入邮箱的文本域,请填写真实的邮件地址。非真实邮件地址,将收不到回复信息。

快速排序算法(Quicksort)

数据结构与算法 清风 341℃ 0评论

一、排序算法(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)

喜欢 (0)or分享 (0)
支付宝扫码打赏 微信打赏
发表我的评论
取消评论

CAPTCHA Image
Reload Image
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址