数据结构---排序算法(比较排序)

目录

插入排序

冒泡排序

希尔排序

 选择排序

堆排序

归并排序

快速排序

插入排序

void Inser_Sort(int A[],int N)
{int i,p;for(p=1; p<N; p++){int tmp=A[p];//从第二个元素开始插，出队。for(i=p; i>0&&A[i-1]>tmp; i--)A[i]=A[i-1];//往后移位A[i]=tmp;//入队。}
}

冒泡排序

void Bubble_Sort(int A[],int N)
{for(int p=N-1; p>=0; p--){int flag=0;for(int i=0; i<p; i++)//一趟冒泡{if(A[i]>A[i+1]){swap(A[i],A[i+1]);flag=1;//有交换}}if(flag==0)break;//无交换}
}

希尔排序

void Shell_Sort(int a[],int N)
{int d,i,p,tmp;for(d=N/2; d>0; d/=2){for(p=d; p<N; p++){tmp=a[p];for(i=p; i>=d&&a[i-d]>tmp; i-=d)a[i]=a[i-d];a[i]=tmp;}}}

 选择排序

void Selecttion_Sort(int A[],int N)
{int Min;for(int i=0; i<N; i++){Min = i;for (int j=i; j<N; j++)if(A[j]<A[Min])Min=j;//堆排序主要是对这一步进行优化。swap(A[i],A[Min]);}
}

堆排序

void Perdown(int a[],int i,int N)
{int child,tmp;for(tmp=a[i]; 2*i+1<N; i=child){child=2*i+1;if(child!=N-1&&a[child+1]>a[child])child++;if(tmp<a[child])a[i]=a[child];else break;}a[i]=tmp;
}void Heap_Sort(int A[],int N)
{int i;for(i=N/2-1; i>=0; i--)Perdown(A,i,N);//创建大顶堆for(i=N-1; i>0; i--)//每次把大顶堆的堆顶元素移到最后{swap(A[0],A[i]);Perdown(A,0,i);}
}

归并排序

void merge(int a[],int tmp[],int l,int r,int rend){int lend = r-1;int p = l;int num = rend - l + 1;while(l<=lend && r <= rend){if(a[l] <= a[r])tmp[p++] = a[l++];else tmp[p++] = a[r++],cnt+=lend-l+1;//计算逆序数。l~lend都与a[r]逆序}while(l<=lend) tmp[p++] = a[l++];while(r<=rend) tmp[p++] = a[r++];for(int i = 0;i<num;++i,rend--){a[rend] = tmp[rend];}
}void msort(int a[],int tmp[],int l,int rend){int m;if(l<rend){m = l+rend>>1;msort(a,tmp,l,m);msort(a,tmp,m+1,rend);merge(a,tmp,l,m+1,rend);}
}void merge_sort(int a[],int n){int tmp[n];msort(a,tmp,0,n-1);
}

快速排序

STL关于快排的几点优化：

1、选主元

2、量少的时候，改为插入排序

3、递归层次大的时候改用堆排序

具体的参考《STL源码剖析》

void Inser_Sort(int A[],int N)
{int i,p;for(p=1; p<N; p++){int tmp=A[p];//从第二个元素开始插，出队。for(i=p; i>0&&A[i-1]>tmp; i--)A[i]=A[i-1];//往后移位A[i]=tmp;//入队。}
}
int Median3(int A[],int Left,int Right)
{int Center =(Left+Right)/2;if(A[Left]>A[Right])swap(A[Left],A[Right]);if(A[Left]>A[Center])swap(A[Left],A[Center]);if(A[Center]>A[Right])swap(A[Center],A[Right]);swap(A[Center],A[Left]);return A[Right-1];
}
void Quicksort(int A[],int Left,int Right)
{   int Cutoff=10;if(Cutoff<=Right-Left)//数据量比较小，递归带来的代价更大;几近有序的情况下，插入排序更为优秀{int Pivot=Median3(A,Left,Right);//选主元  选首位中的中间值int i=Left,j=Right;while(1){while(A[++i]<Pivot);while(A[--j]>Pivot);if(i<j)swap(A[i],A[j]);else  break;}swap(A[Left],A[j]);if(Left<j)Quicksort(A,Left,j);if(j+1<Right)Quicksort(A,j+1,Right);}else Inser_Sort(A+Left,Right-Left);
}