用于贝壳排序的C++程序-yiteyi-C++库

在shellSort中，我们将数组h排序为一个较大的h值。我们不断减小h值，直到它变为1。如果每个h元素的所有子列表都已排序，则称数组为h排序。

null

                     // C++ implementation of Shell Sort                   
                     #include <iostream>                   
                             
                     /* function to sort arr using shellSort */                   
                     void                               shellSort(                               int                               arr[],                               int                               n)                   
                     {                   
                                         // Start with a big gap, then reduce the gap                   
                                         for                               (                               int                               gap = n / 2; gap > 0; gap /= 2) {                   
                                         // Do a gapped insertion sort for this gap size.                   
                                         // The first gap elements arr[0..gap-1] are already in gapped order                   
                                         // keep adding one more element until the entire array is                   
                                         // gap sorted                   
                                         for                               (                               int                               i = gap; i < n; i += 1) {                   
                                         // add arr[i] to the elements that have been gap sorted                   
                                         // save arr[i] in temp and make a hole at position i                   
                                         int                               temp = arr[i];                   
                             
                                         // shift earlier gap-sorted elements up until the correct                   
                                         // location for arr[i] is found                   
                                         int                               j;                   
                                         for                               (j = i; j >= gap && arr[j - gap] > temp; j -= gap)                   
                                         arr[j] = arr[j - gap];                   
                             
                                         // put temp (the original arr[i]) in its correct location                   
                                         arr[j] = temp;                   
                                         }                   
                                         }                   
                     }                   
                             
                     void                               printArray(                               int                               arr[],                               int                               n)                   
                     {                   
                                         for                               (                               int                               i = 0; i < n; i++)                   
                                         std::cout << arr[i] <<                               " "                               ;                   
                                         std::cout <<                               ""                               ;                   
                     }                   
                             
                     int                               main()                   
                     {                   
                                         int                               arr[] = { 12, 34, 54, 2, 3 };                   
                                         int                               n =                               sizeof                               (arr) /                               sizeof                               (arr[0]);                   
                             
                                         std::cout <<                               "Array before sorting: "                               ;                   
                                         printArray(arr, n);                   
                             
                                         shellSort(arr, n);                   
                             
                                         std::cout <<                               "Array after sorting: "                               ;                   
                                         printArray(arr, n);                   
                     }                   

输出：

Array before sorting: 
12 34 54 2 3 
Array after sorting: 
2 3 12 34 54

请参阅完整的文章贝壳类更多细节！

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章