首页 > 代码库 > C#快速排序详解
C#快速排序详解
使用快速排序法对一列数字进行排序的过程
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
步骤为：
- 从数列中挑出一个元素，称为 "基准"（pivot），
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆放在基准的后面（相同的数可以到任一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作。
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个演算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
C#算法实现
using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace 快速排序 //***对相同元素, 不稳定的排序算法***{ //相对来说，快速排序数值越大速度越快 。 快速排序是所有排序里面最快的 class Program { static void Main(string[] args) { int[] arr = { 15, 22, 35, 9, 16, 33, 15, 23, 68, 1, 33, 25, 14 }; //待排序数组 QuickSort(arr, 0, arr.Length - 1); //调用快速排序函数。传值(要排序数组，基准值位置，数组长度) //控制台遍历输出 Console.WriteLine("排序后的数列："); foreach (int item in arr) Console.WriteLine(item); } private static void QuickSort(int[] arr, int begin, int end) { if (begin >= end) return; //两个指针重合就返回，结束调用 int pivotIndex = QuickSort_Once(arr, begin, end); //会得到一个基准值下标 QuickSort(arr, begin, pivotIndex - 1); //对基准的左端进行排序 递归 QuickSort(arr, pivotIndex + 1, end); //对基准的右端进行排序 递归 } private static int QuickSort_Once(int[] arr, int begin, int end) { int pivot = arr[begin]; //将首元素作为基准 int i = begin; int j = end; while (i < j) { //从右到左，寻找第一个小于基准pivot的元素 while (arr[j] >= pivot && i < j) j--; //指针向前移 arr[i] = arr[j]; //执行到此，j已指向从右端起第一个小于基准pivot的元素，执行替换 //从左到右，寻找首个大于基准pivot的元素 while (arr[i] <= pivot && i < j) i++; //指针向后移 arr[j] = arr[i]; //执行到此,i已指向从左端起首个大于基准pivot的元素，执行替换 } //退出while循环,执行至此，必定是 i= j的情况（最后两个指针会碰头） //i(或j)所指向的既是基准位置，定位该趟的基准并将该基准位置返回 arr[i] = pivot; return i; } }}
C#快速排序详解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。