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

秒速五厘米 2022-12-29 06:37 205阅读 0赞

## 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 */