C# quick sort

C# Quick sort

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Sort
{
    class QuickSorter
    {
        private static int[] myArray;
        private static int arraySize;
        public static int[] Sort(int[] a)
        {
            arraySize = a.Length;
            QuickSort(a, 0,arraySize- 1);
	    return a;
        }
        private static void QuickSort(int[] myArray, int left, int right)
        {
            int i, j, s;
            if (left < right)
            {
                i = left - 1;
                j = right + 1;
                s = myArray[(i + j) / 2];
                while (true)
                {
                    while (myArray[++i] < s) ;
                    while (myArray[--j] > s) ;
                    if (i >= j)
                        break;
                    Swap(ref myArray[i], ref myArray[j]);
                }
                QuickSort(myArray, left, i - 1);
                QuickSort(myArray, j + 1, right);
            }
        }
        private static void Swap(ref int left, ref int right)
        {
            int temp;
            temp = left;
            left = right;
            right = temp;
        }
    }
}

The idea of ​​quick sort:

Assume that the array to be sorted is A[0]...A[N-1], first select any data (usually Select the first number of the array) as the key data, then put all numbers smaller than it in front of it, and put all numbers larger than it in behind it. This process is called a quick sort. It is worth noting that quick sort is not a stable sorting algorithm, that is, the relative positions of multiple identical values ​​may change at the end of the algorithm.

The algorithm of one-pass quick sorting is:

1) Set two variables i and j. When sorting starts: i=0, j=N-1;

2) Use the first array element as the key data and assign it to key, that is, key=A[0];

3) Search forward starting from j, that is, search forward from the back (j- -), find the first value A[j] that is less than key, and exchange the item whose value is key with A[j];

4) Search backward starting from i, that is, starting from the front and going backward Search (i++), find the first A[i] that is greater than key, and exchange the item with the value of key with A[i];

5) Repeat step 3

6) Repeat steps 3, 4, and 5 until i=j; (In steps 3 and 4, no value that meets the conditions is found, that is, when A[j] in 3 is not less than key, and A[j] in 4 is not greater than key Change the values ​​of j and i so that j=j-1 and i=i+1 until a value that meets the conditions is found. When exchanging, the i and j pointer positions remain unchanged. The process must be exactly when i+ or j- is completed, at which point the loop ends).

Example:

Take an array as an example, and take the first number in the range as the base number.

## i = 3; j = 7; .

Start from j and search forward. When j=5, if the conditions are met, dig out a[5] and fill it into the previous hole, a[3] = a[5]; i++;

Start from i and search backward. When i=5, exit because i==j.

At this time, i = j = 5, and a[5] happens to be the hole dug last time, so fill X into a[5].

The array becomes:

The above is the content of C# quick sort. For more related content, please pay attention to the PHP Chinese website (www.php.cn)!