排序（堆排序，快排，归并，希尔）-蒲公英云

排序（堆排序，快排，归并，希尔）

1.堆排序

#include <bits/stdc++.h>
using namespace std;
void Adjust_Heap( int A[], int k , int n ) {  //调整大顶堆
    for ( ; k*2 <= n ; k *= 2 ) { 
        int t = 2*k;
        if( t < n && A[t] < A[t+1] ) t ++; // t<n确保有右孩子
        if( A[t] > A[k] )  swap( A[t], A[k] );
        else break;
    }
}
void Create( int A[], int n ) { 
    for ( int i = n/2; i > 0 ; i --) { 
        Adjust_Heap( A, i, n );
    }
}
void Heap_Sort( int A[], int n ) { 
    Create( A, n );
    while( n > 1) { 
        swap( A[1], A[n] );
        Adjust_Heap( A, 1 , --n );
    }
}
int main() { 
    int n;
    scanf("%d", &n);
    int A[n+1];
    for ( int i = 1; i <= n; i ++ )
        scanf("%d", &A[i]);
    int num = n;
    Heap_Sort( A, n );
    for ( int i = 1; i <= num; i ++ )
        printf("%d ", A[i]);
    return 0;
}
/* 10 23 12 13 44 55 21 89 76 67 9 */

2.快速排序

#include <bits/stdc++.h>
using namespace std;
int Partition( int A[], int left, int right) { 
    int init = left;
    int pivot = A[left];
    while ( left < right ) { 
        while ( left < right && A[right] >= pivot ) --right;
        while ( left < right && A[left] <= pivot ) ++left;
        if( left < right)
            swap(A[left],A[right]);
    }
    swap(A[init], A[left]);     // 由于先做的是从右往左的查找，所以最后出来的位置，值是小于pivot，就可以交换pivot与A[left]
    return left;
}
void Quick_Sort( int A[], int left, int right ) { 
    if ( left < right) { 
        int pivot_pos = Partition(A, left, right);
        Quick_Sort( A,left, pivot_pos-1 );
        Quick_Sort( A, pivot_pos+1, right );
    }
}
int main() { 
    int n;
    scanf("%d", &n);
    int A[n+1];
    for ( int i = 1; i <= n; i ++ )
        scanf("%d", &A[i]);
    Quick_Sort(A, 1, n );
    for ( int i = 1; i <=n; i ++ )
        printf("%d ", A[i]);
    return 0;
}
/* 10 23 12 13 44 55 21 89 76 67 9 */

3.归并排序

#include <bits/stdc++.h>
using namespace std;
void Merge( int A[], int B[], int left, int mid, int right ) { 
    for ( int i = left ; i <= right; i ++ )
        B[i] = A[i];
    int i = left, j = mid+1, k = left;
    while ( i<=mid && j<=right ) { 
        if( B[i] <= B[j] )
            A[k++] = B[i++];
        else
            A[k++] = B[j++];
    }
    while ( i <= mid ) A[k++] = B[i++];
    while ( j<= right ) A[k++] = B[j++];
}
void Merge_Sort( int A[], int B[], int left, int right ) { 
    if ( left < right ) { 
        int mid = (left + right ) /2;
        Merge_Sort( A, B, left, mid );
        Merge_Sort( A, B, mid+1, right );
        Merge( A, B, left, mid, right );
    }
}
int main() { 
    int n;
    scanf("%d", &n);
    int A[n+1], B[n+1];
    for ( int i = 1; i <= n; i ++ )
        scanf("%d", &A[i]);
    Merge_Sort(A, B, 1, n );
    for ( int i = 1; i <=n; i ++ )
        printf("%d ", A[i]);
    return 0;
}
/* 10 23 12 13 44 55 21 89 76 67 9 */

4.希尔排序

#include <bits/stdc++.h>
using namespace std;
void Shell_Sort( int A[], int n ) { 
    for ( int dk = n/2; dk >= 1; dk /= 2 ) {  //模拟步长变化
        for ( int i = dk+1; i <= n; i ++ ) { 
            if(  A[i] < A[i-dk] ) { 
                A[0] = A[i];
                int j = i-dk;
                for ( ;j>0 && A[0]<A[j]; j -= dk )
                    A[j+dk] = A[j];
                A[j+dk] = A[0];
            }
        }
    }
}
int main() { 
    int n;
    scanf("%d", &n);
    int A[n+1], B[n+1];
    for ( int i = 1; i <= n; i ++ )
        scanf("%d", &A[i]);
    Shell_Sort( A, n );
    for ( int i = 1; i <=n; i ++ )
        printf("%d ", A[i]);
    return 0;
}
/* 10 23 12 13 44 55 21 89 76 67 9 */