冒泡排序给cpu干懵了 哈哈 还有希尔排序 算法补充（学习笔记）

直接给出代码 

#include
#include
#include "Student.h"
#include "sorttesthelper.h"
#include "BubbleSort.h"
using namespace std;
 
 
template<typename T>
void shellSort(T arr[], int n){
 
    // 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...
    int h = 1;
    while( h < n/3 )
        h = 3 * h + 1;
 
    while( h >= 1 ){
 
        // h-sort the array
        for( int i = h ; i < n ; i ++ ){
 
            // 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
            T e = arr[i];
            int j;
            for( j = i ; j >= h && e < arr[j-h] ; j -= h )
                arr[j] = arr[j-h];
            arr[j] = e;
        }
 
        h /= 3;
    }
}
 
template<typename T >
 
void selectionSort( T arr[], int n){
    for(int i = 0 ; i < n ; i++){
 
        //寻找【i，n之间的最小值】
        int minIndex = i;
        for( int j = i + 1 ; j < n ; j++)
            if(arr[j] < arr[minIndex] )
                minIndex = j;
 
        swap( arr[i] , arr[minIndex]);
 
    }
}
 
//对插入排序来说，直接从第二个元素开始
 
template<typename T >
void InsertSort( T arr[], int n){
    for(int i = 1 ; i < n ; i++){
 
        T e = arr[i];
 
        // j 需要保存元素e应该插入的位置
        int j;
        //寻找【i应该插入的位置】，但是注意我们是从后面往前找所以j 要从后往前
        
        // for( int j = i  ; j > 0 ; j --)
        //     if(arr[j] < arr[j - 1] )
        //         swap(arr[j], arr[j-1]);
        //     else 
        //         break;
        //插入排序的优点是 可以提前 终止循环 所以对于几乎有序的序列 插入排序的性能非常强
        for( j = i  ; j > 0 && arr[j-1] > arr[e]; j --)
                arr[j] = arr[j-1];
        arr[j] = arr[e];
            
 
       
 
    }
}
 
 
int main()
{
    int a[5] = {5,62,3,58,44};
    selectionSort( a, 5 );
    for( int i = 0 ; i < 5 ; i++)
        cout<" ";
    
    cout<
    
    float b[4] = {4.4,2.3,5.63};
    selectionSort( b , 3);
    for( int i = 0 ; i < 3 ; i++)
        cout<" ";
    cout<
 
    string c[2] = {"z","b"};
    selectionSort( c , 2);
    for( int i = 0 ; i < 2 ; i++)
        cout<" ";
    cout<
 
    Student d[3] = {{"D",90} , {"C",89} , { "B", 114}};
    selectionSort( d , 3);
    for( int i = 0 ; i < 3 ; i++)
        cout<
    cout<
 
 
    int n = 100000;
    int *arr1 = SortTestHelper :: generateRandomArr(n, 0, n) ;
    int *arr2 = SortTestHelper :: copyIntArray(arr1, n);
    int *arr3 = SortTestHelper :: generateNearlyorderedArr(n, 100);
 
    int *arr4 = SortTestHelper::copyIntArray(arr1, n);
    int *arr5 = SortTestHelper::copyIntArray(arr1, n);
    // InsertSort(arr2, n);
    // SortTestHelper :: printarr(arr2, n);
    // selectionSort( arr, n );
    // SortTestHelper :: printarr(arr, n);
    // SortTestHelper::test_sort("selection Sort", selectionSort, arr,n);
    SortTestHelper::test_sort("Insertion Sort", InsertSort, arr2,n);
    SortTestHelper::test_sort("Insertion Sort a nearly ordered arr", InsertSort, arr3,n);
    SortTestHelper::test_sort("Bubble Sort", bubbleSort, arr4, n);
    SortTestHelper::test_sort("Shell Sort", shellSort, arr5, n);
 
    delete[] arr1;
    delete[] arr2;
    delete[] arr3;
    delete[] arr4;
    delete[] arr5;
    
    
 
    return 0;
 
}
 
 

下面是单独的冒泡排序 

https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/02-Sorting-Basic/Course%20Code%20(C%2B%2B)/Optional-03-Shell-Sort/main.cpp

给出大佬的链接

//
// Created by liuyubobobo on 7/15/16.
//
 
#ifndef OPTIONAL_02_SHELL_SORT_BUBBLESORT_H
#define OPTIONAL_02_SHELL_SORT_BUBBLESORT_H
 
#include 
#include 
 
using namespace std;
 
template<typename T>
void bubbleSort( T arr[] , int n){
 
    int newn; // 使用newn进行优化
 
    do{
        newn = 0;
        for( int i = 1 ; i < n ; i ++ )
            if( arr[i-1] > arr[i] ){
                swap( arr[i-1] , arr[i] );
 
                // 记录最后一次的交换位置,在此之后的元素在下一轮扫描中均不考虑
                newn = i;
            }
        n = newn;
    }while(newn > 0);
}
 
#endif //OPTIONAL_02_SHELL_SORT_BUBBLESORT_H