排序

C++中的sort函数，头文件algorithm,sort(c.begin(),c.end(),rule);c表示容器，rule表示排序规则，排序规则见C++ 排序规则函数的写法

快速排序: 以首元素为基准点，将比基准点小的元素交换到基准点前面，比基准点大的元素交换到基准点后面，于是形成两段需要排序的新的区域，分别递归。

template<typename T>
void quickSort(T* a, int l, int r){
	if(l<r){
		int i=l, j=r, x=a[l];
		while(i<j){
			while(i<j&&x<a[j])j--;
			if(i<j)a[i++]=a[j];
			while(i<j&&x>a[i])i++;
			if(i<j)a[j--]=a[i];
		}
		a[i]=x;
		quickSort(a, l, i-1);
		quickSort(a, i+1, r);
	}
}

归并排序：数组依次以2个元素、4个元素、。。。为一组合并组内的两个有序数组，直到合并的元素涉及整个数组。原地排序链表采用归并排序，迭代思想的写法：

template<typename T>
T* mergeSort(T* arr, int n, T* na){
	for(int k=1; k<n; k*=2){
		for(int i=0; i<n; i+=2*k){
			int j=0, m=0, o=i;
			while(j<k&&m<k&&i+j<n&&i+k+m<n){
				T ne;
				if(arr[i+j]<=arr[i+k+m])ne=arr[i+j],j++;
				else ne=arr[i+k+m],m++;
				na[o++]=ne;
			}
			while(j<k&&i+j<n)na[o++]=arr[i+j],j++;
			while(m<k&&i+k+m<n)na[o++]=arr[i+k+m],m++;
		}
		T* tmp=arr;
		arr=na, na=tmp;//swap(arr,na);
	}
	return arr;
}

递归思想的写法：

void mergeSortRecursive(int* nums,int l, int r){
	if(l==r-1)return;
	int mid=(l+r)/2;
	mergeSortRecursive(nums,l,mid);
	mergeSortRecursive(nums,mid,r);
	int* na=(int*)malloc((r-l)*sizeof(int));
	int l1=l,r1=mid,j=0;
	while(l1<mid&&r1<r){
		if(nums[l1]<nums[r1])na[j++]=nums[l1++];
		else na[j++]=nums[r1++];
	}
	while(l1<mid)na[j++]=nums[l1++];
	while(r1<r)na[j++]=nums[r1++];
	for(int i=0;i<r-l;i++){
		nums[l+i]=na[i];
	}
	free(na);
}

，利用归并排序的思路计算数组中的逆序对总数，以迭代思想为例，res不断累加两个一组的逆序对数量，累加后升序排序组内元素，然后四个一组。。。快速计算逆序对的方法：当前组分为两半，前面半组k个元素有一个指针l，后面半组k个元素有一个指针r，若[l]>[r]，停下来res+=k-l，r++

参考链接：剑指 Offer 51. 数组中的逆序对

创建于2022.4.1/9.48，修改于2022.4.7/10.30

#sort