排序方法

编程技术  /  houtizong 发布于 3年前   44

/* 排序算法：冒泡，选择，插入，希尔，快速，归并，堆排序 */#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++;    }}//冒泡排序法1void 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;            }        }    }}//冒泡排序法2void 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;            }        }    }}//选择排序法1void 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;    }}//选择排序法2void 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;   //插入元素到相应的位置    }}//插入排序法2void 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;}