[数据结构与算法]2021-08-12排序笔记

1、稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序。

2、非稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。

3、原地排序：原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。

4、非原地排序：需要利用额外的数组来辅助排序。

c++函数输入参数为数组时怎么求长度

https://blog.csdn.net/qq_40692109/article/details/102766573

https://blog.csdn.net/hengbao4/article/details/53224080

1.选择排序：

第一趟找到最小的数和第一个元素交换，第二趟在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置…依次选择

个人认为简便版本：（该版本相等元素不会交换，为稳定排序）

template<class T>
void SelectSort(T &a){
	int n=sizeof(a)/sizeof(int);
	for(int i=0;i<n-1;i++){//总共n-1趟
		for(int j=i+1;j<n;j++){//每趟需要比较的次数n-1-i
			if(a[j]<a[i]){
				int temp=a[i];
				a[i]=a[j];
				a[j]=temp;
			}
	    }
    }
}

"官方"版本：

for (int i = 0; i < n - 1; i++) {
	int min = i;
	for (int j = i + 1; j < n; j++) {
    	if(a[min] > a[j]) min = j;
	}
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

2.冒泡排序：

把第一个元素与第二个元素比较，如果第一个比第二个大，则交换他们的位置…这样一趟比较交换下来之后，排在最右的元素就会是最大的数。

除去最右的元素，我们对剩余的元素做同样的工作，如此重复直到排序完成。

template<class T>
void BubbleSort(T &a){
	int n=sizeof(a)/sizeof(int);
	for(int i=0;i<n-1;i++){//总共n-1趟
        bool flag = 1;
		for(int j=0;j<n-1-i;j++){//每趟需要比较的次数n-1-i,即逐渐-1
			if(a[j]>a[j+1]){//大则向后交换
                flag = 0;
				int temp=a[j+1];
				a[j+1]=a[j];
				a[j]=temp;
			}	
		}
        if(flag) break;//一趟下来若flag没改变，即没发生交换，退出循环
	}
}

flag为优化，若一趟遍历后相邻的元素都没有发生交换，意味着此时的数组已经是有序的，无需再对剩余的元素重复比较下去了。

3.插入排序：

当我们给无序数组做排序的时候，为了要插入元素，我们需要腾出空间，将其余所有元素在插入之前都向右移动一位，这种算法我们称之为插入排序，可以想一下打扑克牌时的手牌整理。

void InsertSort(T &a){
	int n=sizeof(a)/sizeof(int);
	for(int i=1;i<n;i++){//从第二个元素开始
		int now=a[i],j;//记录待插入元素，等下还要放回 
		for(j=i-1;j>=0;j--){
			if(a[j]>now){//判断有序区是否有大于待插入元素的 
				a[j+1]=a[j];
			}
			else break; 	
		}
		a[j+1]=now;//放回待插入元素 
	}
}

4.希尔排序:

希尔排序的思想是采用插入排序的方法，先让数组中任意间隔为 h 的元素有序，刚开始 h 的大小可以是 h = n / 2,接着让 h = n / 4，让 h 一直缩小，当 h = 1 时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的了。

template<class T>
void ShellSort(T &a){
	int n=sizeof(a)/sizeof(int);
	for(int h=n/2;h>0;h/=2){ //对每组间隔为h的分组进行排序，刚开始 h=n/2;
		for(int i=h;i<n;i++){ //对各个局部分组进行插入排序,下面即为插入排序的嵌套，修改了间隔h
			int temp=a[i],j;
			for(j=i-h;j>=0 && a[j]>temp;j-=h){
				a[j+h]=a[j];
			}
			a[j+h]=temp;
		}
	} 
}

**? ? ? **对各个分组进行插入的时候并不是先对一个组排序完了再来对另一个组排序，而是轮流对每个组进行排序。

5.快速排序：

从数组中选择一个元素作为中轴元素，然后把数组中所有小于中轴元素的元素放在其左边，所有大于或等于中轴元素的元素放在其右边，此时中轴元素所处的位置的是有序的，无需再移动中轴元素的位置。从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素)，通过递归的方式，让中轴元素左边的数组和右边的数组也重复同样的操作，直到数组的大小为1，此时每个元素都处于有序的位置。

void quicksort(int a[],int l,int r){
	int i=l,j=r,flag=a[(l+r)/2],tmp;
	do{
		while(a[i]<flag)i++;//从左找比中间哨兵大的数
		while(a[j]>flag)j--;//从右找比中间哨兵小的数
		if(i<=j){
			tmp=a[i];
			a[i]=a[j];
			a[j]=tmp;
			i++;j--;
		}
	}while(i<=j);
	if(l<j){
		quicksort(a,l,j);
	}
	if(i<r){
		quicksort(a,i,r);
	}
}