算法基础学习笔记——①排序

void quick_sort(int q[], int l, int r)//简单理解：这里的l一般0,r一般是个数-1（减去第0个数）
{
     if (l >= r) return;//排序首先看边界，如果区间里没有数或只有一个数则不用排序，否则如下进行上述的1，2，3点
     int i = l - 1, j = r + 1 ,x = q[l + r >> 1];//问：为什么不是i=l,j=r?答：因为是先移动完指针再进行判断，因此指针要先放在两个指针的左右两侧一格，这样往中间移动一格后才能到正真的边界，注意：这里的i,j,l,r都为下标。
     while (i < j) 
     {
         do i ++ ; while (q[i] < x);//指针移动的判断不带等号，因为如果选取的x是数组里最大的数，那么一直满足q[i]<=x,i会一直++发生越界都不会停下，j同理。eg.123，选取3，i<=3,i++,i=3也会向后继续移动，已越界，错误，故此不能加=
         do j -- ; while (q[j] > x);
         if (i < j) swap(q[i], q[j]);//如果这两个指针还没有相遇，则交换，如果不用swap可以写：int t=q[i];q[i]=q[j];q[j]=t;
     }
     quick_sort(q, l, j);
     quick_sort(q, j + 1, r);//eg.1 2排序:
}

#include<bits/stdc++.h> 
using namespace std;
void quick_sort(int q[], int l, int r)
{
     if (l >= r) return;
     int i = l - 1, j = r + 1 ,x = q[l + r >> 1];
     while (i < j) 
     {
         do i ++ ; while (q[i] < x);
         do j -- ; while (q[j] > x);
         if (i < j) swap(q[i], q[j]);
     }
     quick_sort(q, l, j);
     quick_sort(q, j + 1, r);
}
int main()
{
	int a[5]={5,3,2,8,6};//对5，3，2，8，6进行排序 
	quick_sort(a,0,4);//传入数组，传入l,r进行快速排序 
	for(int i;i<5;i++)
	{
		cout<<a[i]<<" ";	//快速排序结果为：23568 
	}
	return 0;
}

void merge_sort(int q[], int l, int r)
{
	int tmp[5];//可变
	if (l >= r) return;
	int mid = l + r >> 1;
	merge_sort(q, l, mid);//l是左半边起点
	merge_sort(q, mid + 1, r);//mid+1是右半边起点
	int k = 0, i = l, j = mid + 1;
	while (i <= mid && j <= r)//i,j分别是左右两边的指针
	   if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];//tmp[k++]=q[i++]等价于tmp[k]=q[i],k++,i++
	   else tmp[k ++ ] = q[j ++ ];//比较q[i],q[j],哪个小就把哪个放到tmp里（最后tmp的顺序就可以从小到大依次排）
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];//把左右两边没有循环完的数放到最后（因为左右两边本身就已经从小到大排好序故这些数一定从小到大）
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];//将tmp里的数复制回q中
}

#include<bits/stdc++.h> 
using namespace std;
void merge_sort(int q[], int l, int r)
{
	int tmp[5];
	if (l >= r) return;
	int mid = l + r >> 1;
	merge_sort(q, l, mid);
	merge_sort(q, mid + 1, r);
	int k = 0, i = l, j = mid + 1;
	while (i <= mid && j <= r)
	   if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
	   else tmp[k ++ ] = q[j ++ ];
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
int main()
{
	int a[5]={8,3,2,7,6};//对5，3，2，8，6进行排序 
	merge_sort(a,0,4);//传入数组，传入l,r进行快速排序 
	for(int i;i<5;i++)
	{
		cout<<a[i]<<" ";	//快速排序结果为：23568 
	}
	return 0;
}