快速排序算法(顺序、倒序)
排序算法比较次数越少,复杂度越低,速度越快。快速排序算法就是一种尽量减少比较次数的算法,它的效率在常用的排序算法中名列前茅,被广泛应用于各类排序,下面先从它的基本思想开始,逐步认识它。
一、快速排序算法的基本思想
快速排序采用分冶的思想,把待排序的数组(或 List列表)分为若干部分,第一次比较把数组分为两部分,第二次采用递归分为四部分,一直分到排序完成为止。
二、C#快速排序算法(顺序)
/// <summary>
/// 快速排序
/// </summary>
/// <param name="arr">待排序数组</param>
/// <param name="left">数组左边下标(索引)</param>
/// <param name="right">数组右边下标</param>
public void QuickSort(int[] arr, int left, int right)
{
int temp;
//如果左边索引小于右边,则排序还未完成
if (left < right)
{
//取中间的元素作为比较基准,小于它的往左移,大于它的往右移
int middle = arr[(left + right) / 2];
int i = left - 1;
int j = right + 1;
while (true)
{
while (arr[++i] < middle && i < right) ;//从左边寻找比中间值小的元素
while (arr[--j] > middle && j > 0) ;//从右边寻找比中间值大的元素
if (i >= j)
break;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
QuickSort(arr, left, i - 1);
QuickSort(arr, j + 1, right);
}
}
调用方法:
int[] a = new int[] { 21, 5, 57, 105, 66, 15, 163, 98 };
QuickSort(a, 0, 7);
foreach (int n in a)
label.Text += n.ToString() + " ";
输出结果:5 15 21 57 66 98 105 163(测试通过)
三、C#快速排序算法(倒序)
倒序跟顺序基本相同,只是元素移方向相反,只需把 while (arr[++i] < middle && i < right) 中的第一个 < 改为 > 、while (arr[--j] > middle && j > 0) 中的第一个 > 改为 < 即可,代码如下:
/// <summary>
/// 快速排序(倒序)
/// </summary>
/// <param name="arr">待排序数组</param>
/// <param name="left">数组左边下标(索引)</param>
/// <param name="right">数组右边下标</param>
public void QuickSort(int[] arr, int left, int right)
{
int temp;
//如果左边索引小于右边,则排序还未完成
if (left < right)
{
//取中间的元素作为比较基准,小于它的往右移,大于它的往左移
int middle = arr[(left + right) / 2];
int i = left - 1;
int j = right + 1;
while (true)
{
while (arr[++i] > middle && i < right) ;//从左边寻找比中间值小的元素
while (arr[--j] < middle && j > 0) ;//从右边寻找比中间值大的元素
if (i >= j)
break;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
QuickSort(arr, left, i - 1);
QuickSort(arr, j + 1, right);
}
}
调用方法:
int[] a = new int[] { 21, 5, 57, 105, 66, 15, 163, 98 };
QuickSort(a, 0, 7);
foreach (int n in a)
label.Text += n.ToString() + " ";
输出结果:163 105 98 66 57 21 15 5(测试通过)
四、C语言快速排序算法(顺序)
#include <stdio.h>
#include <stdlib.h>
void QuickSort(int a[], int left, int right)
{
int i = left;
int j = right;
int temp = a[i];
if( left < right)
{
while(i < j)
{
while(a[j] >= temp && i < j)
{
j--;
}
a[i] = a[j];
while(a[i] <= temp && i < j)
{
i++;
}
a[j] = a[i];
}
a[i] = temp;
QuickSort(a, left, i - 1);
QuickSort(a, j + 1, right);
}
}
void main ()
{
int a[8] = {21, 5, 57, 105, 66, 15, 163, 98};
QuickSort(a, 0, 7);
int i;
for (i = 0; i < 8; i++)
printf("%d,",a[i]);
printf("\n");
}
输出结果:5,15,21,57,66,98,105,163
五、C语言快速排序算法(倒序)
#include <stdio.h>
#include <stdlib.h>
void QuickSort(int a[], int left, int right)
{
int i = left;
int j = right;
int temp = a[i];
if( left < right)
{
while(i < j)
{
while(a[j] <= temp && i < j)
{
j--;
}
a[i] = a[j];
while(a[i] >= temp && i < j)
{
i++;
}
a[j] = a[i];
}
a[i] = temp;
QuickSort(a, left, i - 1);
QuickSort(a, j + 1, right);
}
}
void main()
{
int a[8] = {21, 5, 57, 105, 66, 15, 163, 98};
QuickSort(a, 0, 7);
int i;
for (i = 0; i < 8; i++)
printf("%d,",a[i]);
printf("\n");
}
输出结果:163,105,98,66,57,21,15,5
-
相关阅读
- Hashtable排序的几种方法(C#)
- Excel排序的11个实例,含多条件、按单元格与字体颜色
- Excel分类汇总怎么用的6个操作,含两个字段汇总与汇总
- javascript 多维数组定义、添加、删除和排序元素(js
- 选择排序算法(顺序、倒序)
- js数组操作大全(带实例),含隐性定义、三种添加和删
- 2.23 Word 2016 段落排序
- Excel HLookUp函数的使用方法,包含首行需排序、返回
- Excel Rank函数怎么用的11个实例,含与Rank.EQ和Ra
- C#文件和文件文件夹按时间、名称排序-顺序与倒序
- 按文件名排序隐藏陷井、注意问题(序号文件名)
- 3.19 Word2016 表格数据排序(单列与