排序方法

/* 排序算法：冒泡，选择，插入，希尔，快速，归并，堆排序 */
#include <iostream>
#include <stdlib.h>

using namespace std;

//声明函数
void displayArray(int[] , int);
void swapValue(int[] , int ,int);
void shellSort(int[] , int);
void popperSort(int[] , int);
void popperSort2(int[] , int);
void chooseSort(int[] , int);
void chooseSort2(int[] , int);
void insertSort(int[] , int);
void insertSort2(int[] , int);
void fastSort(int[] , int , int);
void merge(int[] , int , int , int);
void mergeSort(int[] , int[] , int , int);
void heapSort(int[] , int);
void maxHeapTree(int[] , int);
void maxHeapNode(int[] , int , int);

int main()
{
    int arr[6] = {3,4, 3,52,13,2};
    //displayArray(arr , 10);
    cout << "排序前，数组元素：" << endl;
    displayArray(arr , 6);

    //测试：希尔排序
    shellSort(arr , 6);

    //测试：插入排序法1
    //insertSort(arr , 6);

    //测试：插入排序法2
    //insertSort2(arr , 6);

    //测试：冒泡排序法1
    //popperSort(arr , 6);

    //测试：冒泡排序法2
    //popperSort2(arr , 6);

    //测试：选择排序法1
    //chooseSort(arr , 6);

    //测试：选择排序法2
    //chooseSort2(arr , 6);

    //测试：快速排序
    //fastSort(arr , 0 , 5);

    //测试：归并排序法
    //mergeSort(arr , arr , 0 , 5);

    // 测试：堆排序
    //heapSort(arr , 6);

    cout << "排序后，数组元素：" << endl;
    displayArray(arr , 6);

    return 0;
}

//希尔排序法
void shellSort(int arr[] , int length) {
    int delta[3] = {5, 3 ,1};
    int i = 0;

    while(i < 3) {  //遍历距离数

        int dk = delta[i];

        for(int k = dk; k < length; k++) {

            if(arr[k] < arr[k-dk]) {  //比较相距dk的两个元素大小
                int t = arr[k] , j;   //记录要插入的元素值

                for(j = k-dk; j >= 0 && arr[j]>t; j=j-dk) {  //遍历k-dk前面所有相距dk的元素，决定插入的位置
                    arr[j+dk] = arr[j];   //移动元素
                }

                arr[j+dk] = t;   //癣元素插入到正确的位置

            }
        }

        i++;
    }

}

//冒泡排序法1
void popperSort(int arr[] , int length) {
    int temp;
    for(int i = 0; i < length - 1; i++) {  //记录冒泡排序要遍历数组的次数

        for(int j= length-1; j > i; j--) {  //倒序遍历数组元素

            if(arr[j] < arr[j-1]) {
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
        }
    }
}

//冒泡排序法2
void popperSort2(int arr[] , int length) {
    int temp;

    for(int i = 0; i < length-1; i++) {   //记录冒泡排序要遍历数组的次数

        for(int j = 0; j < length-i+1; j++) {  //正序遍历数组元素

            if(arr[j] > arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

//选择排序法1
void chooseSort(int arr[] , int length) {
    int k , temp;

    for(int i = 0; i < length-1; i++) {  //正序遍历数组

        k = i;   //记录最小值的地址

        for(int j = k+1; j < length; j++) {  //遍历i以后的所有数组元素

            if(arr[k] > arr[j]) {
                k = j;
            }
        }

        temp = arr[k];
        arr[k] = arr[i];
        arr[i] = temp;
    }
}

//选择排序法2
void chooseSort2(int arr[] , int length) {
    int k , temp;

    for(int i = length-1; i > 0; i--) {  //倒序序遍历数组

        k = i;   //记录最大值的地址

        for(int j = k-1; j >= 0; j--) {  //遍历i以后的所有数组元素

            if(arr[k] < arr[j]) {
                k = j;
            }
        }

        temp = arr[k];
        arr[k] = arr[i];
        arr[i] = temp;
    }
}

//插入排序法
void insertSort(int arr[] , int length) {
    int temp , index = 0;   //temp记录要插入的元素值，index记录要插入的位置

    for(int i = 1; i < length; i++) {  //遍历第二个及以后的所有元素
        temp = arr[i];

        if(temp < arr[i-1]) {  //如果当前元素值小于它前一个元素，直接检查下一个元素
            continue;
        }

        for(int j = 0; j < i; j++) {  //在i以前找出插入的位置
            if(arr[j] <= temp) {
                index = j;
                break;
            }
        }

        for(int k = i; k >= index; k--) {   //移动插入位置到i的所有元素
            arr[k] = arr[k-1];
        }

        arr[index] = temp;   //插入元素到相应的位置
    }
}

//插入排序法2
void insertSort2(int arr[] , int length) {
    int temp , index = length-1;   //temp记录要插入的元素值，index记录要插入的位置

    for(int i = length-2; i >= 0; i--) {  //遍历倒数第二个及以前的所有元素
        temp = arr[i];

        if(temp < arr[i+1]) {  //如果当前元素值小于它后一个元素，直接检查下一个元素
            continue;
        }

        for(int j = length-1; j > i; j--) {  //在i以后找出插入的位置
            if(arr[j] <= temp) {
                index = j;
                break;
            }
        }

        for(int k = i+1; k <= index; k++) {   //移动i+1到index的所有元素
            arr[k-1] = arr[k];
        }

        arr[index] = temp;   //插入元素到相应的位置
    }
}

//快速排序
void fastSort(int arr[] , int low , int high) {
    if(low < high) {
        int i = low , j = high;  //使用i,j遍历整个数组区域
        int prvilot = arr[low];  //记录中间值

        //将数组分为两个段，一个段所有值都小于另外一个段
        while(j > i) {

            while(j > i && arr[j] >= prvilot) {
                j--;
            }

            if(j > i)
                arr[i++] = arr[j];

            while(j > i && arr[i] <= prvilot) {
                i++;
            }

            if(j > i)
                arr[j--] = arr[i];
        }
        arr[i] = prvilot;  //将中间值插入到空缺的位置

        //递归调用函数，对子段进行快速排序
        fastSort(arr , low , i);
        fastSort(arr , i+1 , high);
    }
}

//合并两个有序数组
void merge(int a1[] , int a2[] , int low , int middle , int high) {
    int i , j;

    for(i = low , j = middle+1; low<=middle && j <= high; i++) {
        if(a1[low] < a1[j]) {
            a2[i] = a1[low++];
        } else {
            a2[i] = a1[j++];
        }
    }

    for(;low <= middle; i++) {
        a2[i] = a1[low++];
    }

    for(;j <= high; i++) {
        a2[i] = a1[j++];
    }
}

//归并排序
void mergeSort(int a1[] , int a2[] , int low , int high) {
    int m , *temp;
    if(low == high) {
        a2[low] = a1[low];

    } else {
        temp = (int *)malloc((high - low + 1) * sizeof(int));
        m = (high + low) / 2;
        mergeSort(a1 , temp , low , m);
        mergeSort(a1 , temp , m + 1 , high);
        merge(temp , a2 , low , m, high);
        free(temp);
    }
}

// 堆排序
void heapSort(int arr[] , int len) {

    maxHeapTree(arr , len);

    while(len > 0) {
        swapValue(arr , 0 , len - 1);
        maxHeapNode(arr , 1 , --len);
    }
}

// 把整棵树化成大顶堆
void maxHeapTree(int arr[] , int len) {
    /* 在n个数组成的数组中
     * 如果把数组看成一个棵树
     * 则[n/2]+1到第n个都是叶子结点
     * 只需将前n/2个结点为根结点的树化成大顶堆就行了
     */
    for(int x = len/2; x >= 1; x--) {
        maxHeapNode(arr , x , len);
        cout << len/2 << "---";
        displayArray(arr , 6);
    }
}

// 把一个结点化成大顶堆
void maxHeapNode(int arr[] , int index , int len) {

    // 注意数组下标问题
    if(index > 0 && index <= len / 2) {

        int largest = index - 1;

        if(arr[2*index-1] > arr[largest]) {
            largest = 2 * index - 1;
        }

        // 此个要注意2*index可能出现越界
        if(2 * index < len && arr[2*index] > arr[largest]) {
            largest = 2 * index;
        }

        if(largest != index - 1) {
            swapValue(arr , index - 1 , largest);
            maxHeapNode(arr , largest + 1 , len);
        }
    }
}

// 交换数组元素值
void swapValue(int arr[] , int x, int y) {
    int temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}

// 展示数组数据值
void displayArray(int arr[] , int length) {

    for(int i = 0; i < length; i++) {
        cout << arr[i] << "  ";
    }

    cout << endl;
}