排序

作者: Ele_Chen | 来源:发表于2017-03-17 16:26 被阅读0次

【恋上数据结构与算法二】(一)排序(Sorting)
排序-冒泡排序
排序
Java | 10种排序算法
常见的排序
002--20200409刷题
排序
排序 -- 选择/插入
前端基础整理 | 算法基础
Java 常见的 8 种排序算法（内排序）

排序

2017年03月17日15:05:14

选择排序

选择排序思想：外层遍历整个待排数组，内层循环寻找 arr [ i, n )区间最小值索引，在外层循环中将其索引位置元素与arr[ i ]交换位置；并扩大有序数组范围。直至排序完成。

时间复杂度：O(n^2)

稳定性：稳定

/**
 * 选择排序
 *
 * @param arr
 * @param n
 */
template<typename T>
void selectionSort(T arr[], int n) {
    for (int i = 0; i < n; ++i) {

        //寻找[i, n)区间的最小值
        int minIndex = i;
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
      swap(arr[minIndex], arr[i]);
      }
}

插入排序

排序思想：外层遍历整个待排数组，内层循环寻找 arr [ i ] 元素在 arr [ 0, i ）区间内的自己的位置并保证arr [ 0 , i ]有序，扩大有序数组范围。直至排序完成。

时间复杂度：最差：O(n^2)，最好: O(n)，因此在多数nlogn的排序末端（小数据量下）会使用插入排序进行优化

稳定性：稳定

    /**
     * 插入排序
     *
     * @param arr
     * @param n
     */
    template<typename T>
    void insertionSort(T arr[], int n) {
        for (int i = 1; i < n; i++) {
        //每次内层循环找到应该arr[j]的位置
            for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
            
                swap(arr[j], arr[j - 1]);
            }
        }
    }

    /**
     * 插入排序,改进版，利用一个单位空间，将一次交换替换为赋值
     *
     * @param arr
     * @param n
     */
    template<typename T>
    void insertionSortBeat(T arr[], int n) {
        for (int i = 1; i < n; i++) {
            //寻找arr[i]的插入位置
            T nux = arr[i];
            int j;      //保存arr[i]应该的插入位置
            for (j = i; j > 0 && arr[j - 1] > nux; j--) {
                arr[j] = arr[j - 1];
            }
            //将nux 放入其应该存在的位置
            arr[j] = nux;
        }
    }


/**
 * 插入排序,改进版，利用一个单位空间，将一次交换替换为一次赋值.
 * 用途：排序数组部分区间
 *
 * @param arr
 * @param n
 */
template<typename T>
void insertionSortBeat(T arr[], int l, int r) {
    for (int i = l+1; i <= r; i++) {

        //寻找arr[i]的插入位置
        T nux = arr[i];
        int j;      //保存arr[i]应该的插入位置
        for (j = i; j > l && arr[j - 1] > nux; j--) {

            arr[j] = arr[j - 1];
        }
        //将nux 放入其应该存在的位置
        arr[j] = nux;
    }
}

二路归并排序

排序思想：利用分治算法将大问题削减成小问题并对小问题进行解决。先将数组分为左右两段，并递归的分成n段，每段都是一个元素的时候，该数组段就是有序的，在递归返回的时候进行两个有序数组的合并，将会得到排序好的数组。

时间复杂度：O(nlgn)

稳定性：稳定

优化点：1. 在小数据量是采用插入排序进行效率的提升。 2. 在合并两个数组的时候当其前后已经有序的时候直接返回，减少合并次数。

template<typename T>
void __mergeSort(T arr[], int l, int r);

template<typename T>
void __merge(T arr[], int l, int mid, int r);

/**
 * 归并排序
 *
 * @param arr
 * @param n
 */
template<typename T>
void mergeSort(T arr[], int n) {

    __mergeSort(arr, 0, n - 1);
}

//采用arr[l, r]
template<typename T>
void __mergeSort(T arr[], int l, int r) {

    if (l >= r) {
        return;
    }

    int mid = l + (r - l) / 2;

    //递归划左右分子区间
    __mergeSort(arr, l, mid);

    __mergeSort(arr, mid + 1, r);

    //优化点：当要合并的数组前后无序的时候才进行合并，有序直接返回。减少合并次数，提高效率
    if (arr[mid] > arr[mid + 1]) {
        //合并
        __merge(arr, l, mid, r);
    }

}

template<typename T>
//合并两个有序数组（采用额外的辅助空间进行合并）
void __merge(T arr[], int l, int mid, int r) {

    //采用额外空间辅助排序，也可直接在原数组进行排序
    T aux[r - l + 1];
    for (int i = l; i <= r; i++) {
        aux[i - l] = arr[i];
    }


    int i = l, j = mid + 1;
    for (int k = l; k <= r; k++) {

        if (i > mid) {
            arr[k] = aux[j - l];
            j++;
        } else if (j > r) {
            arr[k] = aux[i - l];
            i++;
        } else if (aux[i - l] < aux[j - l]) {
            arr[k] = aux[i - l];
            i++;
        } else {
            arr[k] = aux[j - l];
            j++;
        }
    }
}

template<typename T>
void __merge(T arr[], int l, int mid, int r);

template<typename T>
void __mergeSortBeat(T arr[], int l, int r);

/**
 * 归并排序,优化版
 * 当数据量比较小的时候采用插入排序
 *
 * @param arr
 * @param n
 */
template<typename T>
void mergeSortBeat(T arr[], int n) {

    __mergeSortBeat(arr, 0, n - 1);
}

template<typename T>
//合并两个有序数组（采用额外的辅助空间进行合并）
void __merge(T arr[], int l, int mid, int r) {

    //采用额外空间辅助排序，也可直接在原数组进行排序
    T aux[r - l + 1];
    for (int i = l; i <= r; i++) {
        aux[i - l] = arr[i];
    }


    int i = l, j = mid + 1;
    for (int k = l; k <= r; k++) {

        if (i > mid) {
            arr[k] = aux[j - l];
            j++;
        } else if (j > r) {
            arr[k] = aux[i - l];
            i++;
        } else if (aux[i - l] < aux[j - l]) {
            arr[k] = aux[i - l];
            i++;
        } else {
            arr[k] = aux[j - l];
            j++;
        }
    }
}

//采用arr[l, r]，当排序数据量较小的时候采用插入排序提高效率
template<typename T>
void __mergeSortBeat(T arr[], int l, int r) {

    if (r - l < 15) {
        insertionSortBeat(arr, l, r);
        return;
    }

    int mid = l + (r - l) / 2;

    //递归划左右分子区间
    __mergeSortBeat(arr, l, mid);

    __mergeSortBeat(arr, mid + 1, r);

    //优化点：当要合并的数组前后无序的时候才进行合并，有序直接返回。减少合并次数，提高效率
    if (arr[mid] > arr[mid + 1]) {
        //合并
        __merge(arr, l, mid, r);
    }

}

/**
 * 自低向上的归并排序
 *
 * @tparam T
 * @param arr
 * @param n
 */
template<typename T>
void mergeSortBU(T arr[], int n) {

    //sz 未每次比较的宽度，每完成一圈底部归并，比较宽度变为原来的2倍继续比较，直到宽度超过数组长度
    for (int sz = 1; sz < n; sz += sz) {
        //i 为比较区间的开始位置，每次增加两个比较宽度，进行下部分的比较，保证有两个区间可以进行比较，则第二区间必须存在：i+sz<n
        for (int i = 0; i + sz < n; i += sz + sz) {
            //优化点：1. 对于较小的数据集合使用插入排序；2. 对于已经有序的数组不在进行合并

            //归并操作
            //对arr[i,i+sz-1]和arr[i+sz,i+sz+sz-1]或arr[i+sz,n-1]进行归并,避免越界
            __merge(arr, i, i + sz - 1, min(i + sz + sz - 1, n - 1));
        }
    }

}

/**
 * 自低向上的归并排序加强版
 * 优化点：1. 对于较小的数据集合使用插入排序；2. 对于已经有序的数组不在进行合并
 *
 * @tparam T
 * @param arr
 * @param n
 */
template<typename T>
void mergeSortBUBeat(T arr[], int n) {

    //sz 未每次比较的宽度，每完成一圈底部归并，比较宽度变为原来的2倍继续比较，直到宽度超过数组长度
    for (int sz = 1; sz < n; sz += sz) {

        //i 为比较区间的开始位置，每次增加两个比较宽度，进行下部分的比较，保证有两个区间可以进行比较，则第二区间必须存在：i+sz<n
        for (int i = 0; i + sz < n; i += sz + sz) {

            //优化点：1. 对于较小的数据集合使用插入排序；2. 对于已经有序的数组不在进行合并
            if (sz < 15) {

                //使用插入排序进行优化小数据量排序
                insertionSortBeat(arr, i, min(i + sz + sz - 1, n - 1));
                break;
            }

            //优化点：2. 对于已经有序的数组不在进行合并
            if (arr[i + sz - 1] > arr[i + sz]) {

                //归并操作
                //对arr[i,i+sz-1]和arr[i+sz,i+sz+sz-1]或arr[i+sz,n-1]进行归并,避免越界
                __merge(arr, i, i + sz - 1, min(i + sz + sz - 1, n - 1));
            }
        }
    }
}

快速排序

排序思想：选定一个标定元素，寻找其在排好序数组的位置，将数组分为两部分（三部分），在对剩下的部分进行递归寻找标定元素的位置

时间复杂度：最好：O(nlgn), 最坏:O(n^2); 采用随机化标定选择使时间复杂度期望为O(nlogn).

稳定性：不稳定

优化点：1. 对于较小的数据集合使用插入排序，2：采用二路快速排序优化使其适应近乎有序的数组，3：使用3路快速排序使其适应有大量相同元素的数组

template<typename T>
void __quickSort(T arr[], int l, int r);

template<typename T>
int partition(T arr[], int l, int r);

/**
 * 快速排序
 *
 * @tparam T
 * @param arr
 * @param n
 */
template<typename T>
void quickSort(T arr[], int n) {

    __quickSort(arr, 0, n - 1);
}

//对arr[l,r]部分进行快速排序
template<typename T>
void __quickSort(T arr[], int l, int r) {

//    if(l>=r){
//        return;
//    }

    //优化1：对于较小的数据集合使用插入排序
    if (r - l <= 15) {
        insertionSortBeat(arr, l, r);
        return;
    }


    int p = partition(arr, l, r);

    __quickSort(arr, l, p - 1);
    __quickSort(arr, p + 1, r);
}

//对arr[l,r]部分进行partition操作
//返回p,使得arr[l,p-1]<arr[p];arr[p+1]>arr[p]
template<typename T>
int partition(T arr[], int l, int r) {

    //第一个元素标识为基准
    T v = arr[l];

    //p为基准元素应该在的位置
    int j = l;
    for (int i = l + 1; i <= r; i++) {
        if (arr[i] < v) {
            swap(arr[j + 1], arr[i]);
            j++;
        }
    }
    swap(arr[l], arr[j]);

    return j;
}

template<typename T>
void __quickSortRand(T arr[], int l, int r);

template<typename T>
int partitionRand(T arr[], int l, int r);

/**
 * 随机化快速排序，提高在近乎有序的数组中进行排序的效率
 *
 * @tparam T
 * @param arr
 * @param i
 */
template<typename T>
void quickSortRand(T arr[], int n) {

    srand(time(NULL));
    __quickSortRand(arr, 0, n - 1);
}

//对arr[l,r]部分进行快速排序
template<typename T>
void __quickSortRand(T arr[], int l, int r) {

    //优化1：对于较小的数据集合使用插入排序
    if (r - l <= 15) {
        insertionSortBeat(arr, l, r);
        return;
    }


    int p = partitionRand(arr, l, r);

    __quickSortRand(arr, l, p - 1);
    __quickSortRand(arr, p + 1, r);
}

//对arr[l,r]部分进行partition操作
//返回p,使得arr[l,p-1]<arr[p];arr[p+1]>arr[p]
template<typename T>
int partitionRand(T arr[], int l, int r) {

    swap(arr[l], arr[rand() % (r - l + 1) + l]);

    //第一个元素标识为基准
    T v = arr[l];

    //j为基准元素应该在的位置
    int j = l;
    for (int i = l + 1; i <= r; i++) {
        if (arr[i] < v) {
            swap(arr[j + 1], arr[i]);
            j++;
        }
    }
    swap(arr[l], arr[j]);

    return j;
}

template<typename T>
void __quickSort2(T arr[], int l, int r);

template<typename T>
int partition2(T arr[], int l, int r);

/**
 * 2路快速排序
 *
 * @tparam T
 * @param arr
 * @param n
 */
template<typename T>
void quickSort2(T arr[], int n) {

    srand(time(NULL));
    __quickSort2(arr, 0, n - 1);
}

template<typename T>
void __quickSort2(T arr[], int l, int r) {

    if (r - l <= 15) {
        insertionSortBeat(arr, l, r);
        return;
    }

    int p = partition2(arr, l, r);

    __quickSort2(arr, l, p - 1);
    __quickSort2(arr, p + 1, r);

}

template<typename T>
int partition2(T arr[], int l, int r) {

    swap(arr[l], arr[rand() % (r - l + 1) + l]);

    T v = arr[l];

    int i = l + 1, j = r;

    while (true) {
        while (i <= r && arr[i] < v) {
            i++;
        }

        while (j >= l + 1 && arr[j] > v) {
            j--;
        }

        if (j < i) {
            break;
        }

        swap(arr[i], arr[j]);
        i++;
        j--;
    }

    swap(arr[l], arr[j]);

    return j;
}

template<typename T>
void __quickSort3Ways(T arr[], int l, int r);

/**
 * 3路快速排序
 *
 * @tparam T
 * @param arr
 * @param n
 */
template<typename T>
void quickSort3Ways(T arr[], int n) {

    srand(time(NULL));
    __quickSort3Ways(arr, 0, n - 1);
}

/**
 * 3路快速排序
 *
 * @tparam T
 * @param arr
 * @param l
 * @param r
 */
template<typename T>
void __quickSort3Ways(T arr[], int l, int r) {

    if (r - l <= 15) {
        insertionSortBeat(arr, l, r);
        return;
    }

    //partition3Ways
    swap(arr[l], arr[rand() % (r - l + 1) + l]);

    T v = arr[l];

    int lt = l;         //arr[l+1, lt] < v
    int gt = r + 1;     //arr[gt, r] > v
    int i = l + 1;      //arr[lt+1, i) == v

    while (i < gt) {

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

    //交换标识位置到其应该存在的位置
    swap(arr[l], arr[lt]);

    __quickSort3Ways(arr, l, lt - 1);
    __quickSort3Ways(arr, gt, r);

}

堆排序

排序思想：动态的数组进行排序，将数组转化为大（小）顶堆，在对顶元素与尾元素交换，并对堆重新转化为大小顶堆。继续交换，转化。

时间复杂度：O(nlgn)

稳定性：不稳定


template<typename T>
void __shiftDown(T arr[], int n, int k)

/**
 * 堆排序
 *
 * @tparam T
 * @param arr
 * @param n
 */
template<typename T>
void heapSort(T arr[], int n) {

    //heapify
    for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
        __shiftDown(arr, n, i);
    }

    //数组元素在减少
    for (int j = n-1; j > 0; j--) {
        swap(arr[0],arr[j]);
        __shiftDown(arr, j, 0);  //j为未排序堆元素个数
    }
}

/**
 * shiftDowm(调整堆)
 *
 * @tparam T
 * @param arr
 * @param n
 * @param k
 */
template<typename T>
void __shiftDown(T arr[], int n, int k) {

    T v = arr[k];
    while (2 * k + 1 < n) {

        int j = k * 2 + 1;
        if (j + 1 < n && arr[j + 1] > arr[j]) {
            j += 1;
        }
        if ( v >= arr[j] ) {
            break;
        }
        arr[k] = arr[j];
        k = j;
    }
    arr[k] = v;
}