Home  >  Article  >  Backend Development  >  How to write quick sort algorithm using C#

How to write quick sort algorithm using C#

王林
王林Original
2023-09-19 15:28:41561browse

How to write quick sort algorithm using C#

How to use C# to write a quick sort algorithm

The quick sort algorithm is an efficient sorting algorithm. Its idea is to divide the array into smaller ones through the idea of ​​divide and conquer. sub-problems, then recursively solve these sub-problems, and finally combine them to get the solution to the entire problem.

Below we will introduce in detail how to use C# to write a quick sort algorithm and give relevant code examples.

  1. Algorithm idea
    The idea of ​​quick sort can be summarized into the following three steps:
  2. Select a benchmark element, usually the first element of the array;
  3. Place the elements in the array that are smaller than the base element to the left of the base element, and place the elements that are larger than the base element to the right of the base element;
  4. Perform recursive fast recursions on the subarrays to the left and right of the base element respectively Sort.
  5. Specific implementation
    The following is the specific implementation code of the quick sort algorithm written in C#:
using System;

class QuickSort
{
    // 快速排序方法
    public static void Sort(int[] arr, int low, int high)
    {
        if (low < high)
        {
            // 将数组划分成两部分
            int partitions = Partition(arr, low, high);

            // 分别对划分后的两部分进行递归排序
            Sort(arr, low, partitions - 1);
            Sort(arr, partitions + 1, high);
        }
    }

    // 划分数组,并返回划分位置
    public static int Partition(int[] arr, int low, int high)
    {
        int pivot = arr[low]; // 基准元素
        int left = low;
        int right = high;

        while (left < right)
        {
            // 从右往左找到第一个小于基准元素的元素
            while (left < right && arr[right] >= pivot)
                right--;

            // 交换元素位置
            if (left < right)
                Swap(arr, left, right);

            // 从左往右找到第一个大于基准元素的元素
            while (left < right && arr[left] <= pivot)
                left++;

            // 交换元素位置
            if (left < right)
                Swap(arr, left, right);
        }

        return left;
    }

    // 交换元素位置
    public static void Swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 测试代码
    static void Main(string[] args)
    {
        int[] arr = { 5, 3, 8, 4, 2, 9, 1, 6, 7 };
        Console.WriteLine("原始数组:");
        for (int i = 0; i < arr.Length; i++)
            Console.Write(arr[i] + " ");
        Console.WriteLine();

        Sort(arr, 0, arr.Length - 1);
        
        Console.WriteLine("排序后的数组:");
        for (int i = 0; i < arr.Length; i++)
            Console.Write(arr[i] + " ");
        Console.WriteLine();
    }
}
  1. Example running results
    In the above code, we use I created a test program to quickly sort the array and print out the sorting results.

The running results are as follows:

原始数组:
5 3 8 4 2 9 1 6 7
排序后的数组:
1 2 3 4 5 6 7 8 9

As can be seen from the above example, using C# to write a quick sort algorithm is a relatively simple and efficient method that can help us quickly sort arrays. Sort. You can further modify and expand the above code according to your own needs to adapt to different sorting needs.

Summary
This article introduces how to use C# to write the quick sort algorithm and gives corresponding code examples. Quick sort is an efficient sorting algorithm with good performance, easy to understand and implement, and can be widely used in actual development. I hope this article will be helpful to everyone when learning and using the C# programming language.

The above is the detailed content of How to write quick sort algorithm using C#. For more information, please follow other related articles on the PHP Chinese website!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn