程序开发 > C# > 正文

快速排序算法(顺序、倒序)

亮术网 2020-07-05 本网原创

排序算法比较次数越少,复杂度越低,速度越快。快速排序算法就是一种尽量减少比较次数的算法,它的效率在常用的排序算法中名列前茅,被广泛应用于各类排序,下面先从它的基本思想开始,逐步认识它。

 

一、快速排序算法的基本思想

快速排序采用分冶的思想,把待排序的数组(或 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

本文浓缩标签:排序算法