查找和排序之快速排序
查找和排序的关系是什么？
排序，是指将一系列无序的记录，通过某种方式或者算法，将其变为有序的过程。
查找，是指在某些特定的数据结构中，对给定的值（key），进行查找相应位置的过程。
排序是查找的前提，排序算法的优劣影响着查找的效率！
什么是泛型？
同一种逻辑结构，无论该逻辑结构物理存储是啥，都可以执行相同的操作；
就是编写模板代码来适应任意类型，泛型的好处是使用时不必对类型进行强制转换，它通过编译器对类型进行检查；
什么是快速排序？
快速排序是从冒泡排序中演变过来的算法，但它不同于冒泡排序的是采用的是分治法（每一轮选取一个基准元素，并让比它的大的元素移到一边，比它小的元素移到一边，从而把数列拆解成两个部分），如果是简单的选取第一个元素作为基准元素，当希望将一个逆序的数列排列成顺序的时候，时间复杂度由O（n*logn）退化成了O（n**2），随机的选取一个元素，并让它和首项交换位置可以减少遇到这种情况。选定了基准元素以后，我们要做的就是把其他元素中小于基准元素的都交换到基准元素一边，大于基准元素的都交换到基准元素另一边。 具体如何实现呢？有两种方法。
- 双边循环法
- 单边循环法
//双边循环法C语言代码实现
# include <stdio.h>
int FindPos(int * a, int low, int high);
void QuickSort(int * a, int low, int high);
int main(void)
{
int a[6] = {-1, 89, 0, -23, 678, -43};
int i;
QuickSort(a, 0, 5); //第二个参数表示第一个元素的下标 第三个参数表示最后一个元素的下标
for (i=0; i<6; ++i)
printf("%d ", a[i]);
printf("\n");
return 0;
}
void QuickSort(int * a, int low, int high)
{
int pos;
if (low < high)
{
pos = FindPos(a, low, high);
QuickSort(a, low, pos-1);
QuickSort(a, pos+1, high);
}
}
int FindPos(int * a, int low, int high)
{
int val = a[low];
while (low < high)
{
while (low<high && a[high]>=val)
--high;
a[low] = a[high];
while (low<high && a[low]<=val)
++low;
a[high] = a[low];
}//终止while循环之后low和high一定是相等的
a[low] = val;
return high; //high可以改为low, 但不能改为val 也不能改为a[low] 也不能改为a[high]
}双边循环法
双边循环法：首先选取基准元素pivot，然后设置两个指针left和right分别指向最左和最右。
每轮循环从right开始，让指针指向的元素和基准元素进行比较如果大于或等于时就向左移动，如果小于就停止停止移动将两个指针所指向的元素进行互换，然后切换到left指针，如果left指针所指向元素小于或等于基准元素就向右移动，如果大于就停止移动并让两个指针所指向的元素进行互换。反复循环直到两个指针重合时与基准元素互换。
//双边循环法Java代码实现
public static void quickSort(int[] arr, int startIndex,int endIndex) {
// 递归结束条件：startIndex大于或等于endIndex时
if (startIndex >= endIndex) {
return;
}
// 得到基准元素位置
int pivotIndex = partition(arr, startIndex, endIndex);
// 根据基准元素，分成两部分进行递归排序
quickSort(arr, startIndex, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, endIndex);
}
/**
* 分治（双边循环法）
* @param arr 待交换的数组
* @param startIndex 起始下标
* @param endIndex 结束下标
*/
private static int partition(int[] arr, int startIndex, endIndex) {
// 取第1个位置（也可以选择随机位置）的元素作为基准元素
int pivot = arr[startIndex];
int left = startIndex;
int right = endIndex;
while( left != right) {
//控制right 指针比较并左移
while(left<right && arr[right] > pivot){
right--;
}
//控制left指针比较并右移
while( left<right && arr[left] <= pivot) {
left++;
}
//交换left和right 指针所指向的元素
if(left<right) {
int p = arr[left];
arr[left] = arr[right];
arr[right] = p;
}
}
//pivot 和指针重合点交换
arr[startIndex] = arr[left];
arr[left] = pivot;
return left;
}
public static void main(String[] args) {
int[] arr = new int[] {4,4,6,5,3,2,8,1};
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}单边循环法
单边循环法与双边循环法的代码实现简单的多，只需从数组的一边对元素进行遍历和交换。
首先也是选取基准元素pivot，然后设置一个mark指针指向数列起始位置，它代表的是小于基准元素的区域边界。
现在开始从基准元素的下一个位置的元素开始遍历，如果它大于基准元素就继续遍历，如果它小于就将mark指针右移动一位，再让最新遍历到的元素和mark所指向的元素交换位置
# Python写出来的代码好整齐，比Java简洁好多
def quick_sort(start_index,end_index,array=[]):
# 递归结束的条件
if start_index >= end_index:
return
# 基准元素的位置
pivot_index =partion(start_index,end_index,array)
# 根据基准元素分两部分递归排序
quick_sort(start_index, pivot_index-1,array)
quick_sort(start_index+1, end_index,array)
def partion(start_index,end_index,array):
# 取第一个位置的元素作为基准元素，也可以随机选择
pivot = array[start_index]
mark = start_index
for i in range(start_index+1,end_index+1):
if array[i]< pivot:
mark +=1
p = array[mark]
array[mark] = array[i]
array[i] = p
array[start_index] = array[mark]
array[mark] = pivot
return mark
my_array = list([2, 3, 3, 4, 6, 9, 7, 89, -1, 0, 11])
quick_sort(0, len(my_array)-1, my_array)
print(my_array)非递归实现快速排序
快速排序也可以使用非递归的方法实现，绝大多数的递归逻辑都可以使用栈来实现，递归中代码一层一层的调用本身就使用了一个方法调用栈，每次进入一个新方法就是入栈，每次有方法返回就是出栈。
public static void quickSort(int[] arr, int startIndex,int endIndex) {
// 递归结束条件：startIndex大于或等于endIndex时
if (startIndex >= endIndex) {
return;
}
// 得到基准元素位置
int pivotIndex = partition(arr, startIndex, endIndex);
// 根据基准元素，分成两部分进行递归排序
quickSort(arr, startIndex, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, endIndex);
}
/**
* 分治（双边循环法）
* @param arr 待交换的数组
* @param startIndex 起始下标
* @param endIndex 结束下标
*/
private static int partition(int[] arr, int startIndex,int endIndex) {
// 取第1个位置（也可以选择随机位置）的元素作为基准元素
int pivot = arr[startIndex];
int left = startIndex;
int right = endIndex;
while( left != right) {
//控制right 指针比较并左移
while(left<right && arr[right] > pivot){
right--;
}
//控制left指针比较并右移
while( left<right && arr[left] <= pivot) {
left++;
}
//交换left和right 指针所指向的元素
if(left<right) {
int p = arr[left];
arr[left] = arr[right];
arr[right] = p;
}
}
//pivot 和指针重合点交换
arr[startIndex] = arr[left];
arr[left] = pivot;
return left;
}
public static void main(String[] args) {
int[] arr = new int[] {4,4,6,5,3,2,8,1};
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}和刚才的递归实现相比，非递归方式代码的变动只发生在quickSort方法 中。该方法引入了一个存储Map类型元素的栈，用于存储每一次交换时 的起始下标和结束下标。 每一次循环，都会让栈顶元素出栈，通过partition方法进行分治，并且 按照基准元素的位置分成左右两部分，左右两部分再分别入栈。当栈为空时，说明排序已经完毕，退出循环。
数据结构研究的是数据的存储和数据的操作的一门课；
数据的存储分两部分
- 个体的存储；
- 个体关系的存储；
从某个角度而言，数据的存储最核心的就是个体关系的存储，个体的存储可以忽略不计，就像二叉树里不考虑节点的数据类型一样
写在最后
在郝斌老师视频的帮助下，我从最开始的学习C语言入门，到后来的数据结构入门，感谢郝斌老师的视频，感谢UP主蠢杠杠！数据库和Java我看的其他课程哈^_^。
虽然现在已经是2021年了，但是经典的基础知识点永不过时！我在看数据结构的时候，中间曾有数次间断学习，也曾看过其他的很多有关的课程，但是郝斌老师的课易于理解不像其他课程一样理论知识点繁多，用来入门非常合适。当然，技术飞快更迭有一小部分变化或者说有了更多更新的内容，建议还是要去完善数据结构的知识树，郝斌老师的数据结构课只是给了我们一个不太完整的树干，基础已经打好了，但是需要我们自己去开枝散叶！
感觉可能是视频不全的原因吧，而且最开始由于对指针的理解问题，其实最开始的部分视频不是讲的数据结构，而是带我们复习学习的C语言的指针。对于链表来说，C语言的指针的理解非常重要，我记得最开始我真的看的很头疼，好多次看着看着睡了，好在后来通过线下课程我把C语言又强化了一遍，之后敲起链表来才算得心应手一点。因为我之后看了其他的很多课程，中间由于一些原因又学了Python等内容，觉得对数据结构内容基本了解，就没坚持看了，而现在我看完郝斌老师的课程后我发现郝斌老师的有些讲解让我打开了新世界的大门感觉，对于一个知识，不是说你知道就等于了解了，我之前自已为是的了解其实只是浅显的知道，现在才是理解，而接下来，我还需要不断的实践去深入了解，就像我现在还没法独立的把有些代码手撕出来。我还记得，有次是老师的电脑丢了还是什么，有些视频都是老师熬着夜在家里录得，泪目了！
直到现在，我还是没找好未来的发展方向，在焦虑思考过后也没能找到答案，但是不管未来是怎样，脚踏实地的走好每一步总是没错的，活在当下吧！之后打算把之前学习的内容陆续整理其实也是再学习，上传到博客上，中间也会有新学习的内容上传，希望能坚持吧！
