09-排序1 排序 (25 分)

小灰灰 2021-12-08 23:21 222阅读 0赞

排序算法大汇总，缺少基数排序，需要自己再写一遍

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <cstdio>
      2 #include <stdlib.h>
      3 #include <algorithm>
      4 using namespace std;
      5 const int CUTOFF = 50;
      6 
      7 typedef int ElementType;
      8 
      9 const int maxn = 1e6+1;
     10 
     11 void InsertionSort( ElementType A[], int N )
     12 {
     13     int P, i;
     14     ElementType tmp;
     15     for (P=1; P<N; P++) {
     16         tmp = A[P];
     17         for (i=P; i>=1 && A[i-1]>tmp; i--) {
     18             A[i] = A[i-1];
     19         }
     20         A[i] = tmp;
     21     }
     22 }
     23 
     24 
     25 void ShellSort( ElementType A[], int N )
     26 {
     27     int P, i, D, Si;
     28     ElementType tmp;
     29     int Sedgewick[] = {
         929, 505, 209, 109, 41, 19, 5, 1, 0};
     30     
     31     for (Si = 0; Sedgewick[Si] >= N; Si++);
     32     
     33     for(D = Sedgewick[Si]; Sedgewick[Si] > 0; D = Sedgewick[++Si]) {
     34         for (P=D; P<N; P++) {
     35             tmp = A[P];
     36             for (i=P; i>=D && A[i-D]>tmp; i -= D) {
     37                 A[i] = A[i-D];
     38             }
     39             A[i] = tmp;
     40         }
     41     }
     42 }
     43 
     44 
     45 void Swap( ElementType *a, ElementType *b)
     46 {
     47     int t;
     48     t = *a;
     49     *a = *b;
     50     *b = t;
     51     
     52 }
     53 void PercDown( ElementType A[], int P, int N )
     54 {
     55     
     56     int Parent, Child;
     57     ElementType X;
     58     
     59     X = A[P];
     60     
     61     for (Parent = P; Parent*2+1 <= N-1; Parent = Child) {
     62         Child = Parent * 2 + 1;
     63         if ( Child < (N-1) and A[Child+1] > A[Child] ) {
     64             Child++;
     65         }
     66         if (X > A[Child]) {
     67             break;
     68         }
     69         else {
     70             A[Parent] = A[Child];
     71         }
     72     }
     73     A[Parent] = X;
     74     
     75 }
     76 void HeapSort( ElementType A[], int N)
     77 {
     78     for (int i = (N-1)/2 ; i>=0; i--) {
     79         PercDown(A, i, N);
     80     } //buildMaxHeap
     81     
     82     for(int i=N-1; i>0; i--) {
     83         Swap(&A[0], &A[i]);
     84         PercDown(A, 0, i);
     85     }
     86     
     87 }
     88 
     89 
     90 void Merge( ElementType A[], ElementType TmpA[], int L, int R, int RightEnd )
     91 {
     92     int TmpInd, LeftEnd, NumElements;
     93     TmpInd = L;
     94     LeftEnd = R-1;
     95     NumElements = RightEnd - L + 1;
     96     
     97     while (L <= LeftEnd && R <= RightEnd) {
     98         if (A[L] < A[R]) {
     99             TmpA[TmpInd++] = A[L++];
    100         }
    101         else TmpA[TmpInd++] = A[R++];
    102     }
    103     
    104     while (L <= LeftEnd) {
    105         TmpA[TmpInd++] = A[L++];
    106     }
    107     while (R <= RightEnd) {
    108         TmpA[TmpInd++] = A[R++];
    109     }
    110     for (int i=0; i<NumElements; i++) {
    111         A[RightEnd] = TmpA[RightEnd];
    112         RightEnd--;
    113     }
    114     
    115 }
    116 void Msort( ElementType A[], ElementType TmpA[], int L, int RightEnd)
    117 {
    118     int center;
    119     if (L < RightEnd) {
    120         center = (RightEnd + L) / 2;
    121         Msort(A, TmpA, L, center);
    122         Msort(A, TmpA, center+1, RightEnd);
    123         Merge(A, TmpA, L, center+1, RightEnd);
    124     }
    125 }
    126 //Recursive_mergeSort
    127 void MergeSort( ElementType A[], int N )
    128 {
    129     ElementType * TmpA = (ElementType *) malloc( N * sizeof(ElementType) );
    130     if (TmpA == NULL) {
    131         printf("MEMORY INSUFFICIENT");
    132     }
    133     Msort(A, TmpA, 0, N-1);
    134     free(TmpA);
    135 }
    136 //Non-recursive_mergeSort
    137 void MergeSort2( ElementType A[], int N )
    138 {
    139     int length, i;
    140     ElementType * TmpA;
    141     TmpA = (ElementType *) malloc( N * sizeof(ElementType) );
    142     
    143     for (length = 1; length <= N; length *= 2) {
    144         
    145         for (i = 0; i < N-2*length; i += 2*length) {
    146             Merge(A, TmpA, i, i+length, i+2*length-1);
    147         }
    148         if (i + length < N) {
    149             Merge(A, TmpA, i, i+length, N-1);
    150         }
    151         
    152     }
    153 }
    154 
    155 //"algorithm" function sort(, , )
    156 void LibQuickSort( ElementType A[], int N )
    157 {
    158     sort(A, A+N);
    159 }
    160 
    161 //SelfWritten QSort
    162 
    163 ElementType Median3(ElementType A[], int L, int R)//三元中值法
    164 {
    165     int Center;
    166     Center = (L + R)/2;
    167     if (A[L] > A[Center]) {
    168         Swap( &A[L], &A[Center] );
    169     }
    170     if (A[L] > A[R]) {
    171         Swap( &A[L], &A[R] );
    172     }
    173     if (A[Center] > A[R]) {
    174         Swap( &A[Center], &A[R] );
    175     }
    176     Swap( &A[Center], &A[R-1] );  //Pivot locates at A[R-1]
    177     return A[R-1];
    178 }
    179 void QSort( ElementType A[], int L, int R )
    180 {
    181     int NumEle, Pivot, i, j;
    182     NumEle = R - L + 1;
    183     
    184     if( NumEle >= CUTOFF ){
    185         Pivot = Median3(A, L, R);
    186         i = L + 1 ;
    187         j = R - 2;
    188         
    189         while(1) {
    190             while( A[i] < Pivot && i<R ) i++;
    191             while (A[j] > Pivot && j>L) j--;
    192             if(i < j) Swap(&A[i], &A[j]); //??? ==?
    193             else break;
    194         }
    195         Swap(&A[i], &A[R-1]); //Pivot translocates in A[i];
    196         
    197         QSort(A, L, i-1);
    198         QSort(A, i+1, R);
    199         
    200     }
    201     else InsertionSort(A + L, NumEle);
    202     
    203     
    204 }
    205 void QSort2( ElementType A[], int L, int R )//直接选A[0]
    206 {
    207     int NumEle, Pivot, i, j;
    208     NumEle = R - L + 1;
    209     
    210     if( NumEle >= CUTOFF ){
    211         Pivot = A[L];
    212         i = L ;
    213         j = R + 1 ;
    214         
    215         while(1) {
    216             while( A[++i] < Pivot && i < R);
    217             while (A[--j] > Pivot && j > L);
    218             if(i < j) swap(A[i], A[j]); //??? ==?
    219             else break;
    220         }
    221         swap(A[j], A[L]); //Pivot translocates in A[i];
    222         
    223         
    224         QSort2(A, L, j-1);
    225         QSort2(A, j+1, R);
    226         
    227     }
    228     else InsertionSort(A + L, NumEle);
    229     
    230 }
    231 void QuickSort(ElementType A[], int N)
    232 {
    233     QSort(A, 0, N-1);
    234 }
    235 
    236 
    237 
    238 int arr[maxn];
    239 int main() {
    240     int N;
    241     scanf("%d", &N);
    242     for(int i=0; i<N; i++) {
    243         scanf("%d", arr+i);
    244     }
    245     QuickSort(arr, N);
    246     printf("%d", arr[0]);
    247     
    248     for(int i=1; i<N; i++) {
    249         printf(" %d", *(arr + i ) );
    250     }
    251     printf("\n");
    252     
    253     
    254     return 0;
    255 }

转载于:https://www.cnblogs.com/acoccus/p/10935717.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211209/390c2ccbadf24c8a92196310a2931bb9.png