算法导论1.排序算法
排序算法是最基础的一类算法。主要排序算法包括选择排序、插入排序、冒泡排序、合并排序、堆排序和快速排序。把这些排序算法全部实现一边，再把《算法导论》对应章节后面的习题做一遍，确实是系统学习算法的一个不错的开端。
选择排序
选择排序的想法很简单，把需要排序的数组看成一堆扑克牌：先查一遍，抽出最小的作为第一个张；在剩下的牌堆里再查一遍，选出最小的作为第二个元素……重复直到牌堆耗尽。想法简单的其代价就是运行时间为Θ(n×n)：在查询A、2或3的时候，都要反复地比较其与K、Q的大小，直觉告诉我这样做没有意义。
void selectionSort( int * x, int length){
for ( int i= 0 ;i<length- 1 ;i++ ){
int minValue = INT_MAX;
int minPosition = 0 ;
for ( int j=i;j<length;j++ ){
if (x[j]< minValue){
minValue = x[j];
minPosition = j;
}
}
int temp = x[minPosition];
x[minPosition] = x[i];
x[i] = temp;
}
}
插入排序
插入排序的想法类似于从牌堆中摸牌，并插入到手中已经排序过的牌中。在最外层以i为自变量的循环中，0~i-1张牌就是手中已排序的牌（循环开始时就是第一张牌x[0]），i~length-1张牌就是牌堆，每次循环将第i张牌（也就是牌堆顶部的第一张牌）插入到牌堆中。因为手中的牌已经排好序，所以每次插入都会移动所有比这张待插入的牌大的手牌。这个排序算法的运行时间也很高，为Θ(n×n)。
void insertionSort( int * x, int length){
for ( int i= 1 ;i<length;i++ ){
for ( int j=i;j> 0 ;j-- ){
if (x[j]<x[j- 1 ]){
int temp = x[j];
x[j] =x[j- 1 ];
x[j - 1 ]= temp;
}
}
}
}
合并排序
合并算法是一种递归的算法。假设牌堆已经分成两堆，每一堆都已经排好序，比如一堆是{A,3,4,7,J,K}，另一堆是{2,5,6,8,9,10,Q}，把这两堆合并成一个牌堆的方法很简单，只要依次比较两个牌堆顶部的牌，选择较小的一张加入已排序的牌堆，直到两个牌堆都空了，这个工作的时间代价仅为Θ(n)。如何获得已排序的两个牌堆呢？答案是先直接均分为两堆，再递归地调用自身去对着两堆合并排序，直到问题的规模足够小，比如只剩1张或2张牌。好在将问题分解到足够小需要的递归次数是lgn而不是n，因此该算法的运行时间为Θ(n×lgn)。不过合并排序需要额外的空间开销，换言之它不是一种原地排序算法，他的空间开销为Θ(n×lgn)，而原地排序算法仅仅为Θ(n)。
void mergeSort( int * x, int length){
if (length== 0 || length== 1 ){
return ;
}
int mid = (length- 1 )/ 2 ;
int child1Size = mid+ 1 ;
int * child1 = new int [child1Size];
int child2Size = length-mid- 1 ;
int * child2 = new int [child2Size];
for ( int i= 0 ;i<mid+ 1 ;i++ ){
child1[i] = x[i];
}
for ( int i=mid+ 1 ;i<length;i++ ){
child2[i -mid- 1 ]= x[i];
}
mergeSort(child1,child1Size);
mergeSort(child2,child2Size);
{
int i= 0 ; int j= 0 ; int k= 0 ;
while (k< length){
if (i== child1Size){
x[k] = child2[j];
j ++;k++; continue ;
}
if (j== child2Size){
x[k] = child1[i];
i ++;k++; continue ;
}
if (child1[i]<= child2[j]){
x[k] = child1[i];
i ++;k++; continue ;
}
if (child2[j]< child1[i]){
x[k] = child2[j];
j ++;k++; continue ;
}
}
}
return ;
}
冒泡排序
冒泡排序是一个很简单的原地排序方法：从数组的最后一个元素开始（这个元素就是当前的“泡”）向前遍历，如果前一个元素比当前的“泡”小，那么当前的“泡”就变成了前一个元素；如果前一个元素比当前的“泡”大，那么交换“泡”和该元素的位置（这个“泡”冒上去了）。每一次冒泡到最前面一个元素，都能保证选择了最小的“泡”。虽然该算法运行时间为Θ(n×n)，但是在冒前面的“泡”的过程中，后面的相对较小的元素也一定程度地冒上来了（换言之，这次冒泡并不是“无用功”），使得冒比较大的“泡”时经常只需要检查一下而不用作交换，所以常数因子比较小。
void bubbleSort( int * x, int length)
{
for ( int i= 0 ;i<length;i++ ){
for ( int j=length- 1 ;j> 0 ;j-- ){
if (x[j]<x[j- 1 ]){
int temp = x[j];
x[j] =x[j- 1 ];
x[j - 1 ]= temp;
}
}
}
}
堆排序
堆排序是一种“漂亮”的原地排序方法，其运行时间为Θ(n×lgn)。熟悉了最大堆的特性，堆排序的思路就非常简单了：最大堆的根节点最大，将根节点和堆中的最后一个元素互换位置，并且将堆的长度减去1；此时堆已经不是最大堆，但是根元素的两个子堆仍然是最大堆，将这种堆转化为最大堆的过程heapMax只需要Θ(lgn)时间，那么就转化为最大堆再取次大的元素。由一个杂乱数组建成一个最大堆的过程heapMaxBuild也需要Θ(n×lgn)时间，这不影响总的运行时间量级。
void heapMax( int * xInput, int xSize, int i){
int l=(i+ 1 )* 2 - 1 ;
int r=(i+ 1 )* 2 ;
if (i>= xSize){
return ;
}
if (l>=xSize && r>= xSize){
return ;
}
if (xInput[i]>=xInput[l] && (r>=xSize ? true : (xInput[i]>= xInput[r]))){
return ;
}
int maxI=(r>=xSize ? l : (xInput[l]>xInput[r]? l:r));
int temp = xInput[i];
xInput[i] = xInput[maxI];
xInput[maxI] = temp;
heapMax(xInput, xSize, maxI);
}
void heapMaxBuild( int * x, int length){
for ( int i=length/ 2 + 1 ;i>= 1 ;i-- ){
heapMax(x, length, i - 1 );
}
}
void heapSort( int * x, int length){
heapMaxBuild(x, length);
for ( int i=length;i>= 2 ;i-- ) {
int temp = x[i- 1 ];
x[i - 1 ]=x[ 0 ];
x[ 0 ]= temp;
heapMax(x, i - 1 , 0 );
}
}
快速排序
快速排序的运行时间为Θ(n×lgn)，它是一种原地排序算法。取最后一个元素作为基准，遍历一次数组，将小于基准的元素排在前面，大于基准的元素排在后面，而不在乎同小于或同大于基准的元素之间的顺序。一次遍历之后，将最后一个元素和大于基准的元素的第一个交换位置，则基准前方的都是小于基准的元素，后方都是大于基准的元素，再递归调用自身，对同小于或同大于基准的元素进行快速排序。
int partition( int * x, int p, int r){
int mid = x[r];
int i = p;
for ( int j = p; j <= r - 1 ; j++ ){
if (x[j] <= mid){
int tmp = x[i];
x[i] = x[j];
x[j] = tmp;
i ++ ;
}
}
int tmp = x[i];
x[i] = x[r];
x[r] = tmp;
return i;
}
void quickSort( int * x, int p, int r){
if (p < r){
int q = partition(x, p, r);
quickSort(x, p, q - 1 );
quickSort(x, q + 1 , r);
}
}
作者： 一叶斋主人
出处： HdhCmsTestcnblogs测试数据/yiyezhai
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
标签: 算法
作者： Leo_wl
出处： http://HdhCmsTestcnblogs测试数据/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://haodehen.cn/did47463