//每次用划分函数将数组划分为2部分，接下来递归对2部分进行快速排序。
//选这一段区间中的任意一个数为基准，进行元素交换，并找到一个下标，使下标左边的数都小于基准数，右边的都大于基准数。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
int[] arr = { 6, 2, 1, 7, 7, 1, 3, 7 };
QuickSort(arr, 0, arr.Length - 1);
foreach (int i in arr)
Console.WriteLine(i);
Console.ReadKey();
}
static int Partition(int[] arr, int l, int r)
{
int x = arr[l]; //基准值
l--; r++;
while (true)
{
do
{
l++;
}
while (arr[l] < x); //自左向右找到一个不小于x的元素
do
{
r--;
}
while (arr[r] > x); //自右向左找到一个不大于x的元素
if (l < r) //没有找到划分界限之前
{
//交换2个元素
int t = arr[l];
arr[l] = arr[r];
arr[r] = t;
}
else break; //找到界限了
}
return r; //界限是r
}
static void QuickSort(int[] arr, int l, int r)
{
if (l < r)
{
int t = Partition(arr, l, r);
QuickSort(arr, l, t);
QuickSort(arr, t + 1, r);
}
}
}
}
作者: 红鹰(Jake) 时间: 2014-1-14 22:20
我来蹭一下。作者: 王忠杰 时间: 2014-1-21 21:10
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace test
{
class Program
{
static void Main(string[] args)
{
int[] array = { 49, 38, 65, 97, 76, 13, 27 };
sort(array, 0, array.Length - 1);
Console.ReadLine();
} /* * 一次排序单元，完成此方法，key左边都比key小，key右边都比key大。
* @param array 排序数组
* @param low 排序起始位置
* @param high 排序结束位置
* @return 单元排序后的数组 */
private static int sortUnit(int[] array, int low, int high)
{
int key = array[low];
while (low < high)
{ //从后向前搜索比key小的值
while (array[high] >= key && high > low)
--high; //比key小的放左边
array[low] = array[high]; //从前向后搜索比key大的值，比key大的放右边
while (array[low] <= key && high > low)
++low; //比key大的放右边
array[high] = array[low];
} //左边都比key小，右边都比key大。 //将key放在游标当前位置。 //此时low等于high
array[low] = key;
Console.WriteLine(array.ToString());
return high;
} /* * 快速排序 * @param arry * @return */
public static void sort(int[] array, int low, int high)
{
if (low >= high) return; //完成一次单元排序
int index = sortUnit(array, low, high); //对左边单元进行排序
sort(array, low, index - 1); //对右边单元进行排序
sort(array, index + 1, high); }
}
}作者: yuanlianxi03 时间: 2014-1-21 23:06