C++数据结构复习(二)一一排序算法

先给出排序算法的总结：

关于排序算法可以说我已经是总结了很多次了，但是过不久就会生疏，究其原因还是因为用的少了。而且我希望自己掌握的程度能够到那种随时随地信手拈来。。。可惜。。自己不给力。。希望这次能够彻底掌握吧

这里先给出几个主要的排序，挖个坑吧。。虽然好像挖的坑有点多了我。。

快速排序

~~

void QuickSort(int arr[], int first, int last) {
    int pivot = OnceSort(arr, first, last);
    //已经有轴值了，再对轴值左右进行递归
    QuickSort(arr, first, pivot-1);
    QuickSort(arr, pivot+1, last);
}
void OnceSort(int arr[], int first, int last) {
    int i = first, j = last;
    //当 i < j 时，即移动的点还没到中间时循环
    while (i < j) {
        //从右边区开始，保证 i<j 并且 arr[i] 小于等于 arr[j]的时候就向左遍历
        while (i < j && arr[i] <= arr[j]) --j;
       //这时候已经跳出循环，说明 i > j或者 arr[i] 大于 arr[j]了，如果是如果i<j那
       //就是arr[i]大于arr[j]，那就交换
        if (i < j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        //对左边区执行一样的操作
        while (i < j && arr[i] <= arr[j]) ++i;
        if (i < j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    //返回已经移动的一边当做下次排序的轴值
    return i;
}

---

~~

堆排序

void HeapSort(int arr[], int len) {
    int i;
    //初始化堆，从最后一个父节点开始
    for (i = len / 2 - 1; i >= 0; --i) {
        Heapify(arr, i, len);
    }
    // 从堆中的取出最大元素再调整堆
    for (int i = len - 1; i > 0; --i) {
        int temp = arr[i];
        arr[i] = arr[0];
        arr[0] = temp;
        //调整成堆
        Heapify(arr, 0, i);
    }
}

void Heapify(int arr[], int first, int last) {
    int father = first;
    int son = 2 * father + 1;
    while (son < last) {
        if (son + 1 < last && arr[son] < arr[son + 1])
            ++son;
        // 如果父节点大于子结点则表示调整完毕
        if (arr[father] > arr[son])
            break;
        else {
            // 不然就交换父节点和子节点的元素
            int temp = arr[father];
            arr[father] = arr[son];
            arr[son] = temp;
            // 父和子节点变成下一个要比较的位置
            father = son;
            son = 2 * father + 1;
        }
    }
}

---

插入排序

//插入排序
//这里temp是哨兵位
//从小到大
//时间复杂度 n^2
void InsertSort() {
    int temp;
    int j;
    for (int i = 0; i < 10; i++) {
        temp = b[i];
        for (j = i - 1; j >=0; j--) {
            if (b[j] >temp) {
                b[j+1] = b[j];
            }
            else {
                break;
            }
        }
        b[j+1] = temp;
    }
    cout << "the sort is:";
    for (int i = 0; i < 10; i++) {
        cout << b[i] << "";
    }
    cout << endl;
}

---

冒泡排序

void Bubble(int b[10]) {
    int temp;
    int i;
    for (i = 9; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (b[j] > b[j+1]) {
                temp = b[j];
                b[j] = b[j+1];
                b[j+1] = temp;
            }
        }
    }
    cout<<"the sort is:";
    for(int i=0;i<10;i++) {
        cout<<b[i]<<" ";
    }
    cout<<endl;
}

---