排序
2018-04-20 本文已影响0人
LxxxR
1 快速排序
以a[r]为枢纽,i指针遍历数组,j指针之后的元素都是比a[r]小的元素。
void qsort(int A[],int l,int r){
int i,j;
if(l<r){ //边界检查
for(i=l,j=l;i<=r;i++) {
if(A[i]<=A[r]) // i指针找比枢纽小的
swap(A[i],A[j++]); //找到一对就交换
}
j--; //最后会交换到A[r],j++,所以需要j--
qsort(A,l,j-1);
qsort(A,j+1,r);
}
}
或者
void qsort(int A[],int l,int r){
int i,j;
if(l<r){ //枢纽为最后一个元素
for(i=l,j=l;i<r;i++) {
if(A[i]<=A[r]) // i指针找比枢纽小的
swap(A[i],A[j++]); //找到一对就交换
}
swap(A[r],A[j]); //最后交换A[r]和A[j]
qsort(A,l,j-1);
qsort(A,j+1,r);
}
}
应用:找数组第k小元素 /前k小元素(循环)
int kElement(int k, int nums[]) {
int l=0,r=nums.size()-1;
if(r<0 || k<=0 || k>r+1) return -1;
int i,j;
while(l<=r){
for(i=l,j=l;i<r;i++){
if(nums[i]<=nums[r])
swap(nums[i],nums[j++]);
}
swap(nums[j],nums[r]);
if(j==k-1)
return j;
else if(j>k-1)
r=j-1;
else
l=j+1;
}
}
2 归并排序
递归,前半部分排序,后半部分排序,归并一起。
void mergesort(int a[],int l,int r){
if(l<r){
int m=(l+r)/2; //分成两段
mergesort(a,l,m); //前半段排序
mergesort(a,m+1,r);//后半段排序
merge(a,l,m,r); //两段归并
}
}
void merge(int a[],int l,int m,int r){
vector<int> temp;
int i=l,j=m+1;
while(i<=m && j<=r){
if(a[i]<a[j])
temp.push_back(a[i++]);
else
temp.push_back(a[j++]);
}
while(i<=m) //两个while,只有一个会执行
temp.push_back(a[i++]);
while(j<=r)
temp.push_back(a[j++]);
for(i=l;i<=r;i++)
a[i]=temp[i-l]; //复制回去,注意数组下标
}
3 堆排序
3.1 堆的存储
因为堆是一个完全二叉树,所以用数组来存储。
a[i]的左右子节点分别为:a[2i+1],a[2i+2]。
a[i]的父节点为:a[(i-1)/2]。
所以最后一个有子节点的节点为a[n/2-1]。
从小到大排,需要大根堆,不断把堆顶放在数组后边。
3.2 堆顶的调整
如果一个堆的堆顶被另一个元素替换,该元素需要不断向下调整。
3.3 堆排序
1.初始化堆: 从下 (最后一个有子节点的节点a[n/2-1]) 往上 (a[0]),对每一个节点调整,得到一个大根堆。
2.维护堆:输出堆顶,用最后一个元素替换堆顶(其实是堆顶和最后一个元素交换);堆长度-1,调整堆顶;重复此步骤。
void fixdown(int a[],int n,int i){
int j=2*i+1;
while(j<n){ //从上往下调整,结束的条件:无孩子||该节点比孩子节点大
if(j+1<n && a[j+1]>a[j])
j+=1;
if(a[i]<a[j]){
swap(a[i],a[j]);
i=j;
j=2*i+1;
}
else
break;
}
}
void Heapsort(int a[],int n){
for(int i=n/2-1;i>=0;i--){ //初始化对,从下往上
fixdown(a,n,i);
}
for(int i=n-1;i>=1;i--){ //当前最大值(堆顶)放最后,调整堆顶
swap(a[0],a[i]); //代表要放的位置,也代表交换后数组长度
fixdown(a,i,0);
}
}
3.4 插入
在堆的最后插入一个元素,并调整堆。
将该元素不断向上调整。
void InsertHeapUp(int a[],int value,int n){
int i=n;
a[i]=value; //把value插在最后
int j=(i-1)/2; //a[i]父节点
while(j>=0){ //终止条件:a[i]没有父节点 || a[i]<父节点
if(a[i]<a[j]) //a[i]<父节点,终止
break;
else{
swap(a[i],a[j]);//否则,与父节点交换,继续向上调整
i=j;
j=(i-1)/2;
}
}
}
4 冒泡排序
4.1 普通冒泡排序
第一趟,j=[0,...n-2],把最大值放在a[n-1];
第二趟,j=[0,...n-3],把次大值放在a[n-2]; ...
void bubbleSort(vector<int>& a, int n) {
for (int i = 0; i<n; i++) {
for (int j = 0; j<n - 1 - i; j++) {
if (a[j]>a[j + 1])
swap(a[j], a[j + 1]);
}
}
}
4.2 优化冒泡排序
1,某一趟若未进行过任何交换,则排序结束
void bubbleSort2(vector<int>& a, int n) {
for (int i = 0; i<n; i++) {
bool flag = false;
for (int j = 0; j<n - 1 - i; j++) {
if (a[j]>a[j + 1]) {
swap(a[j], a[j + 1]);
flag = true; //表示交换过
}
}
if (flag == false) break; //这一趟未交换过
}
}
2,记录上一趟最后交换的位置t,t后面的数未进行交换,即有序,这一趟只需对t前面的数排序。
void bubbleSort3(vector<int>& a, int n) {
int lastSwap, lastSwapTemp = n - 1;
//lastSwap代表数组尾部,lastSwapTemp代表最后一次交换的位置
for (int i = 0; i<n; i++) {
lastSwap = lastSwapTemp;
for (int j = 0; j<lastSwap; j++) { //从0到上一次最后交换的位置
if (a[j]>a[j + 1]) {
swap(a[j], a[j + 1]);
lastSwapTemp = j;
}
}
if (lastSwap == lastSwapTemp) break; //这一趟未交换过
}
}
5 插入排序
void insertsort(vector<int>& a,int n){
for(int i=1;i<n;i++)
for(int j=i;j-1>=0 && a[j-1]>a[j];j--)
swap(a[j],a[j-1]);
}