排序算法(C++实现)

冒泡排序

void bubble_sort(int* arr, int n){
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-i-1;j++){
            if(arr[j] > arr[j+1]){
                swap(arr[j],arr[j+1]);
            }
        }
    }
}

选择排序

void selection_sort(int* arr, int n){
    for(int i=0;i<n-1;i++){
        int min_index = i;
        for(int j=i+1;j<n;j++){
            if(arr[j] < arr[min_index]){
                min_index = j;
            }
        }
        swap(arr[i],arr[min_index]);
    }
}

希尔排序

void shell_sort(int* arr, int n){
    for(int gap=n/2;gap>0;gap/=2){
        for(int i=gap;i<n;i++){
            int temp = arr[i];
            int j;
            for(j=i;j>=gap && arr[j-gap]>temp;j-=gap){
                arr[j] = arr[j-gap];
            }
            arr[j] = temp;
        }
    }
}

插入排序

void insertion_sort(int* arr, int n){
    for(int i=1;i<n;i++){
        int key = arr[i];
        int j = i-1;
        while(j>=0 && arr[j]>key){
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

快速排序

void quick_sort(int* arr, int low, int high){
    if(low < high){
        int pivot = arr[high];
        int i = low - 1;
        for(int j=low;j<high;j++){
            if(arr[j] < pivot){
                i++;
                swap(arr[i],arr[j]);
            }
        }
        swap(arr[i+1],arr[high]);
        quick_sort(arr, low, i);
        quick_sort(arr, i+2, high);
    }
}

归并排序

void merge(int* arr, int left, int mid, int right){
    int* temp = new int[right-left+1];
    int i = left, j = mid+1, k = 0;
    while(i <= mid && j <= right){
        if(arr[i] < arr[j]){
            temp[k++] = arr[i++];
        }else{
            temp[k++] = arr[j++];
        }
    }
    while(i <= mid) temp[k++] = arr[i++];
    while(j <= right) temp[k++] = arr[j++];
    for(int i=left, k=0;i<=right;i++,k++){
        arr[i] = temp[k];
    }
    delete[] temp;
}

void merge_sort(int* arr, int left, int right){
    if(left < right){
        int mid = (left + right) / 2;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid+1, right);
        merge(arr, left, mid, right);
    }
}

main

int main(){
    int n = 100000;
    int* arr = generate_data(n);
    // 评判每个算法的排序时间
    clock_t start, end;

    start = clock();
    bubble_sort(arr, n);
    end = clock();
    cout << "Bubble Sort Time: " << (double)(end - start) / CLOCKS_PER_SEC << " seconds" << endl;

    start = clock();
    selection_sort(arr, n);
    end = clock();
    cout << "Selection Sort Time: " << (double)(end - start) / CLOCKS_PER_SEC << " seconds" << endl;

    start = clock();
    shell_sort(arr, n);
    end = clock();
    cout << "Shell Sort Time: " << (double)(end - start) / CLOCKS_PER_SEC << " seconds" << endl;

    start = clock();
    insertion_sort(arr, n);
    end = clock();
    cout << "Insertion Sort Time: " << (double)(end - start) / CLOCKS_PER_SEC << " seconds" << endl;

    start = clock();
    quick_sort(arr, 0, n - 1);
    end = clock();
    cout << "Quick Sort Time: " << (double)(end - start) / CLOCKS_PER_SEC << " seconds" << endl;

    start = clock();
    merge_sort(arr, 0, n - 1);
    end = clock();
    cout << "Merge Sort Time: " << (double)(end - start) / CLOCKS_PER_SEC << " seconds" << endl;

    delete[] arr;
    return 0;
}