static void Main(string[] args)
{
    int[] datas = new int[100000];
    for (int j = 0; j < 100000; j++) {
        datas[j] = r.Next(1, 10000);
    }
    Stopwatch stopwatch = new Stopwatch();
    stopwatch.Start();
    sortArray(0, datas.Length - 1, datas);
    stopwatch.Stop();
    
    foreach (int data in datas) {
        Console.WriteLine(data);
    }

    Console.WriteLine("是否排序好：" + isSort(datas));
    Console.WriteLine("运行时间:" + stopwatch.ElapsedMilliseconds);

    Console.ReadKey();
}

static void sortArray(int start,int end,int[] datas) {

    if (start >= end) {
        return;
    }
            
    int i = start;
    int j = end;
    //左边参考值 ，从小到大排序
    int refer = datas[start];
    while (i != j) {

            //先搜索比参考值小的
        while (datas[j] >= refer && j > i)
        {
            j--;
        }

        while (datas[i] <= refer && i < j) {
            i++;
        }

        if (i < j) {
            //交换
            int temp = datas[i];
            datas[i] = datas[j];
            datas[j] = temp;
        }
    }
        
        //把参考值放到中间相撞位置
    datas[start] = datas[i];
    datas[i] = refer;

    sortArray(start, i - 1, datas);
    sortArray(i + 1, end, datas);
}

static bool isSort(int[] datas) {
    for (int i = 0; i < datas.Length -1; i++) {
        if (datas[i] > datas[i + 1]) {
            return false;
        }
    }

    return true;
}

思想就是，先定一个参考值（左边参考值或右边参考值），这个左右边参考值涉及到先搜索比参考值小的还是比参考值大的。例如，先定一个左边参考值，从右边搜索比参考值小的，再从数据左边开始搜索比参考值大的，然后交换这两个值，一直到这两个搜索撞到了一起。而这个撞在一起的值，就是那个先搜索的（比参考值小），让参考值归为到中间，因为选取参考值时是选取的左边位置，所以，直接交换中间相撞位置和参考值位置就行了。同理的，选取右边参考的话，就要先搜索左边的，先搜索比参考值大的。

模拟排序10W条随机数据用时：20ms，快得飞起啊，而且空间复杂度也低