排序算法

2018-08-17  本文已影响0人  小张同学_loveZY

十大排序算法总结

基础交换函数

void swap(int& temp1, int& temp2)
{
    temp1 = temp1 ^ temp2;
    temp2 = temp1 ^ temp2;
    temp1 = temp1 ^ temp2;
}

冒泡排序

算法流程
复杂度分析
C代码

冒泡排序

void bubbleSort(int array[], int length) 
{

    for (int i = 0; i<length-1; i++)  // 这一步控制步长
    {
        for (int j = 0; j < length -1 -i;j++) // 这一步前后排序
        {
            if (array[j] > array[j+1])
            {
                swap(array[j], array[i]);
            }
        }
    }
}

选择排序

算法流程
复杂度分析
C代码

选择排序

void selectSort(int array[], int length) {
    int minIndex;
    for (int i = 0; i < length - 1; i++) {
        minIndex = i;
        for (int j = i + 1; j < length; j++) {
            if ( array[j] < array[minIndex] ) {     // 寻找最小的数
                minIndex = j;                       // 将最小数的索引保存
            }
        }
        swap(array[i], array[minIndex]);
    }
}

插入排序

算法流程
复杂度分析
C代码

插入排序

void insertSort(int array[], int length)
{
    int preIndex, current;
    for (int i = 1; i < length; i++) {
        preIndex = i - 1;
        current = array[i];
        while (preIndex >= 0 && array[preIndex] > current) {
            array[preIndex + 1] = array[preIndex];
            preIndex--;
        }
        array[preIndex + 1] = current;
    }
}

希尔排序

算法流程
复杂度分析
C代码

希尔排序

void  shellSort(int array[], int length)
{
    int gap = 1, current;
    int i, preIndex;
    while (gap < length / 3) {          // 动态定义间隔序列
        gap = gap * 3 + 1;              // 保证除3的时候会取到1
    }
    for ( ; gap > 0; gap = floor(gap / 3 ) ) {
        // 间隔为gap的直接插入排序,这里除了前几个数外，都需要与之前的比较
        for (i = gap; i < length; i++) {
            current = array[i];
            preIndex = i - gap;
            // 注意取值范围
            while (preIndex >= 0 && array[preIndex] > current) {
                array[preIndex + gap] = array[preIndex];
                preIndex = preIndex - gap;
            }
            array[preIndex + gap] = current;
        }
    }
    
}

归并排序

算法流程
复杂度分析
C代码

合并函数

void merge(int array[], int begin, int middle, int end) {
    int len1 = middle - begin + 1;
    int len2 = end - middle;
    int i, j;
    // 定义中间变量
    int *arr1 = new int[len1 + 1];
    int *arr2 = new int[len2 + 1];

    // 赋初值
    for (i = 0; i < len1; i++)
    {
        *(arr1 + i) = array[begin + i];
    }
    for (j = 0; j < len2; j++)
    {
        *(arr2 + j) = array[middle + j + 1];
    }
    // 设置哨兵
    arr1[len1] = 10000;
    arr2[len2] = 10000;

    // 从最前面遍历
    i = 0;
    j = 0;
    for (int k = begin; k <= end; k++)
    {
        if (arr1[i] < arr2[j])
        {
            array[k] = arr1[i];
            i++;
        }
        else
        {
            array[k] = arr2[j];
            j++;
        }
    }

    delete arr1;
    delete arr2;
}

归并排序

void mergeSort(int array[], int begin, int end)
{
    int middle = floor((end + begin) / 2);
    // 先分后和
    if (begin < end) {
        mergeSort(array, begin, middle);
        mergeSort(array, middle + 1, end);
        merge(array, begin, middle, end);
    }

}

快速排序

算法流程
复杂度分析
C代码

快速排序

void quickSort(int array[], int left, int right)
{

    if (left < right) {
        int temp = array[left];
        int indexL = left;
        int indexR = right;
        while (indexR > indexL)
        {
            // 只要有涉及下标运算，都需要判断
            // 右振荡
            while (indexR > indexL && array[indexR] >= temp)
            {
                indexR--;
            }
            if(indexR > indexL)
                array[indexL++] = array[indexR];

            // 左振荡
            while (indexR > indexL  && array[indexL] < temp)
            {
                indexL++;
            }
            if (indexR > indexL)
                array[indexR--] = array[indexL];
        }

        // 计算完后 indexR = indexL = 最中间的下标 
        array[indexR] = temp;

        // 递归
        quickSort(array, left, indexR - 1);
        quickSort(array, indexR + 1, right);
    }

}

堆排序

算法流程
复杂度分析
C代码

堆排序

void adjustHeap(int array[], int len)
{
    int maxIndex, rootIndex, subLeftIndex, subRightIndex;
    // 从下往上调整
    for (int i = len / 2; i > 0; i--){
        // C的下标从0开始
        rootIndex = i - 1;
        maxIndex = rootIndex;
        subLeftIndex = 2 * i -1;  
        subRightIndex = 2 * i;
        if (array[maxIndex] < array[subLeftIndex])
            maxIndex = subLeftIndex;
        // 右子节点需要判断是否越界
        if ( subRightIndex< len && array[maxIndex] < array[subRightIndex])
            maxIndex = subRightIndex;
        // 根节点与最大节点交换
        if( maxIndex != rootIndex)
            swap(array[rootIndex], array[maxIndex]);
    }
}

void heapSort(int array[], int len)
{
    int adjustLen = len;
    for (int i = 0; i < len - 1 ; i++) {
        adjustHeap(array, adjustLen);
        // C的下标从0开始的
        swap(array[0], array[adjustLen-1]);
        adjustLen--;
    }

}

计数排序

算法流程
复杂度分析
C代码

计数排序

void countSort(int array[], int len)
{

    int minValue = array[0];
    int maxValue = array[0];
    // 获得最小最大值，确定排序边界
    for (int i = 1; i < len; i++) {
        if (array[i] < minValue)
            minValue = array[i];
        if (array[i] > maxValue)
            maxValue = array[i];
    }
    
    int countLen = maxValue - minValue + 1;
    int * countArray = new int[countLen];
    // 清0
    for (int i = 0; i < countLen; i++) {
        countArray[i] = 0;
    }
    // 计算数目
    for (int i = 0; i < len; i++) { 
        countArray[array[i] - minValue] ++;
    }

    // 计算数目
    int j = 0;
    for (int i = 0; i < countLen; i++) {
        while ( countArray[i] != 0 )
        {
            array[j++] = i + minValue;
            countArray[i]--;
        }
    }

    delete countArray;
}

桶排序

算法流程
复杂度分析
C代码

基数排序

算法流程
复杂度分析
C代码
上一篇 下一篇

猜你喜欢

热点阅读