2020-08-21 算法合集

1. 冒泡排序

/**
 * 冒泡排序
 * @param array
 * @param len
 */
void bubbleSore(int array[], int len) {
    for (int i = 0; i < len - 1; ++i) {
        for (int j = 0; j < len - i - 1; ++j) {
            if (array[j] > array[j + 1]) {
                std::swap(array[j], array[j + 1]);
            }
        }
    }
}

2.选择排序

/**
 * 选择排序
 * @param array
 * @param len
 */
void selectSore(int array[], int len) {
    for (int i = 0; i < len; ++i) {
        int min_index = i;
        for (int j = i; j < len; ++j) {
            if (array[min_index] > array[j]) {
                min_index = j;
            }
        }
        std::swap(array[min_index], array[i]);
    }
}

3. 插入排序

/**
 * 插入排序啊
 */
void insertSore(int array[], int len) {
    int i, j;
    for (i = 1; i < len; ++i) {
        int tmp = array[i];
        for (j = i; j > 0 && array[j - 1] > tmp; --j) {
//            if (array[j - 1] > tmp) {
            array[j] = array[j - 1];
//            } else {
//                break;
//            }
        }
        array[j] = tmp;
    }
}

4. 希尔排序

/**
 * 希尔排序
 * @param array
 * @param len
 */
void shellSore(int array[], int len) {
    int inCount = len / 2;
    do {
        int i, j, k;
        for (i = 0; i < inCount; ++i) {
            for (j = i + inCount; j < len; j += inCount) {
                int tmp = array[j];
                for (k = j; k > i && array[k - inCount] > tmp; k -= inCount) {
                    array[k] = array[k - inCount];
                }
                array[k] = tmp;
            }
        }
        inCount /= 2;
    } while ((inCount > 0));
}

5. 归并排序(递归实现)

void _merge(int array[], int l, int mid, int r) {
    int tmp[r - l + 1];
    for (int i = l; i <= r; ++i) {
        tmp[i - l] = array[i];
    }

    int i = l;
    int j = mid + 1;
    int k = l;
    for (; k <= r; ++k) {
        if (i > mid) {
            array[k] = tmp[j - l];
            j++;
        } else if (j > r) {
            array[k] = tmp[i - l];
            i++;
        } else if (tmp[i - l] < tmp[j - l]) {
            array[k] = tmp[i - l];
            i++;
        } else {
            array[k] = tmp[j - l];
            j++;
        }
    }

}

void _mergeSore(int array[], int l, int r) {
    if (l >= r) {
        return;
    }
    int mid = (l + r) >> 1;
    _mergeSore(array, l, mid);
    _mergeSore(array, mid + 1, r);

    _merge(array, l, mid, r);
}

/**
 * 归并排序
 * @param array 
 * @param len 
 */
void mergeSore(int array[], int len) {
    _mergeSore(array, 0, len - 1);
}

6. 快速排序(递归实现)

int _partition(int array[], int l, int r) {
    int index = rand() % (r - l + 1) + l;
    std::swap(array[l], array[index]);
    int v = array[l];
    int p = l;
    for (int i = l; i <= r; ++i) {
        if (array[i] < v) {
            std::swap(array[p + 1], array[i]);
            p++;
        }
    }
    std::swap(array[l], array[p]);
    return p;
}

void _quickSore(int array[], int l, int r) {
    if (l >= r) {
        return;
    }
    int p = _partition(array, l, r);
    _quickSore(array, l, p - 1);
    _quickSore(array, p + 1, r);
}

//快速排序
void quickSore(int array[], int len) {
    srand(time(NULL));
    _quickSore(array, 0, len - 1);
}

6.1 快排（三路快排）

void _quickSore3way(int array[], int l, int r) {
    if (l >= r) {
        return;
    }
    int index = rand() % (r - l + 1) + l;
    std::swap(array[l], array[index]);
    int v = array[l];

    int lt = l;
    int gt = r + 1;
    int i = l;

    while (gt > i) {
        if (array[i] > v) {
            std::swap(array[gt - 1], array[i]);
            gt--;
        } else if (array[i] < v) {
            std::swap(array[lt + 1], array[i]);
            lt++;
            i++;
        } else {
            i++;
        }
    }

    std::swap(array[l], array[lt]);

    _quickSore3way(array, l, lt - 1);
    _quickSore3way(array, gt, r);
}

//三路快排
void quickSore3way(int array[], int len) {
    srand(time(NULL));
    _quickSore3way(array, 0, len - 1);
}

7. 堆排序

void adjustmentArray(int array[], int index, int len) {
    while (index * 2 + 1 < len) {
        int max = 2 * index + 1;
        if (max + 1 < len && array[max] < array[max + 1]) {
            max = max + 1;
        }
        if (array[index] > array[max]) {
            break;
        }
        swap(array[index], array[max]);
        index = max;
    }
}

/**
 * 堆排序
 * @param array
 * @param len
 */
void heapSort(int array[], int len) {
    //调整最大堆
    for (int i = (len / 2) - 1; i >= 0; --i) {
        adjustmentArray(array, i, len);
    }
    for (int i = len - 1; i > 0; --i) {
        std::swap(array[0], array[i]);
        adjustmentArray(array, 0, i);
    }
}