快速排序算法

源代码地址：GitHub - firstsaofan/Data-structure-and-algorithm at develop

本来准备一天刷一个算法的，看到这里才发现基本上是一章一个算法，今天我倒是看完了第四章

但是并没有吃透，需要继续编写C#代码实现。

这本书是python作为例子不太适合我，python高度封装的方法显得代码很少，本人没有学过python，这对我来说理解算法会有阻碍，准备去找个网址或者换一本书。

def quick_sort(data):    
    """快速排序"""    
    if len(data) >= 2:  # 递归入口及出口        
        mid = data[len(data)//2]  # 选取基准值，也可以选取第一个或最后一个元素        
        left, right = [], []  # 定义基准值左右两侧的列表        
        data.remove(mid)  # 从原始数组中移除基准值        
        for num in data:            
            if num >= mid:                
                right.append(num)            
            else:                
                left.append(num)        
        return quick_sort(left) + [mid] + quick_sort(right)    
    else:        
        return data
 
# 示例：
array = [2,3,5,7,1,4,6,15,5,2,7,9,10,15,9,17,12]
print(quick_sort(array))
# 输出为[1, 2, 2, 3, 4, 5, 5, 6, 7, 7, 9, 9, 10, 12, 15, 15, 17]
快速排序—>一种常用的优雅的排序算法。快速排序使用分而治之的策略。

分而治之（D&C divide and conquer）

def sum(list):
 if list == []:
    return 0
return list[0] + sum(list[1:])
Tips
s = "abcde"

print(s[:1])//a [0,1) 相当于打印第一个字符
print(s[2:])//cde 索引2--所有

思路：找一个基准值然后根据这个值把这个数组分成左边是小于这个基准值的数组，右边是大于这个基准值的数组，然后分别把这两个数组重复上述，直到子数组只有1个元素

以下是一次执行流程

image-1669218853996

//快速排序法 分而治之
//tips 编写涉及数组的递归函数时，基线条件往往是数组为空或者只包含一个元素。陷入困境时，请检查基线条件是不是这样的。

//找到基线条件

int[] arr = { 15, 22, 35, 9, 16, 33, 15, 23, 68, 1, 33, 25, 14 }; //待排序数组
QuickSort(arr, 0, arr.Length - 1);  //调用快速排序函数。传值(要排序数组，基准值位置，数组长度)

//控制台遍历输出
Console.WriteLine("排序后的数列：");
foreach (int item in arr) {
    Console.WriteLine(item);
}

static void QuickSort(int[] arr, int begin, int end)
{
    if (begin >= end) { 
    return;
    }
    var pivotIndex = GetPivot(arr, begin, end);

    QuickSort(arr, begin, pivotIndex-1);
    QuickSort(arr, pivotIndex+1, end);
}

static int GetPivot(int[]arr,int begin, int end) { 
    //获取基准值索引
    var i = begin;
    var j= end;
    //取第一个元素作为基准值
    var pivot = arr[begin];
    while (i < j)
    {
        //先从右边找比基准值小的值
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        //跳出循环的条件就是找到了基准值小的值
        arr[i]=arr[j];//把右边的小的值甩到前面去

        //先从左边找比基准值大的值
        while (i < j && arr[i] <= pivot)
        {
            i++;
        }
        //跳出循环的条件就是找到了基准值大的值
        arr[j] = arr[i];//把左边的大的值甩到后面去
    }
    //跳出循环的时候i=j 也就是基准值在的地方
    arr[i] = pivot;
    return i;  
}

Console.WriteLine("Hello, World!");
总结：

根据基准值来划分左右（小大）子数组， 然后一直重复直到子数组元素为1，结束。

i,j可以理解一个定位器或者指针。

上节递归小结：

使用战虽然方便，但是也要付出代价，存储详尽的信息可能占用大量的内存。每个函数调用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量的函数调用的信息。在这种情况下，你有两种选择。

1.重新编写代码，转而使用循环。

2.使用尾递归。这是一个高级递归主题，不在本书的讨论范围。另外，并非所有的语言都支持尾递归。

总结

1.递归指的是调用自己的函数

2.每个递归函数都有两个条件：基线条件和递归条件。

3.栈有两种操作：压入和弹出。

4.所有的函数调用都进入调用栈

5.调用栈可能很长，这将占用大量的内存。

后面应该会跟着算法导论过一遍算法或者跟着某机构的算法视频过一遍。