即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

整数排序

编程语言 u010150046 16℃ 0评论

给一组整数,按照升序排序。使用归并排序,快速排序,堆排序或者任何其他 O(n log n) 的排序算法。

此题主要是回顾一下三种O(Nlog(N))复杂度的算法,以后面试可能会用到,要能保证在短时间内能够写出来这些算法,所以直接贴代码:

int partition1(vector<int>&A,int low,int high){
        int temp = A[low];
        while (low < high){
            while (low < high && A[high] > temp)high--;
            A[low] = A[high];
            while (low < high && A[low] <= temp)low++;
            A[high] = A[low];
        }
        A[low] = temp;
        return low;
    }

    void quickSort(vector<int>& A,int low,int high){
        if (low < high){
            int index = partition1(A, low, high);
            quickSort(A, low, index - 1);
            quickSort(A, index + 1, high);
        }
    }
    void sortIntegers2(vector<int>& A) {
        quickSort(A, 0, A.size() - 1);
    }

    //归并排序
    void merge(vector<int>& A, int low, int mid, int high, vector<int>& temp){
        int i = low, j = mid + 1;
        int index = 0;
        while (i <= mid && j <= high){
            if (A[i] < A[j]){
                temp[index] = A[i];
                i++;
            }
            else{
                temp[index] = A[j];
                j++;
            }
            index++;
        }
        while (i <= mid)temp[index++] = A[i++];
        while (j <= high)temp[index++] = A[j++];
        for (int k = 0; k < index; k++){
            A[k + low] = temp[k];
        }
    }

    void mergeSort(vector<int>& A, int low, int high,vector<int>& temp){
        if (low < high){
            int mid = low + (high - low)/ 2;
            mergeSort(A, low, mid, temp);
            mergeSort(A, mid + 1, high, temp);
            merge(A, low, mid, high, temp);
        }
    }

    void sortIntegers2(vector<int>& A) {
        vector<int> temp(A.size());
        mergeSort(A, 0, A.size() - 1, temp);
    }

    //堆排序
    void heap_down(vector<int>& A, int k, int len){
        int temp = A[k];
        for (int j = 2 * k + 1; j < len; j = 2 * j + 1){
            if (j < len - 1 && A[j + 1] > A[j])j++;
            if (temp < A[j]){
                A[k] = A[j];
                k = j;
            }
            else break;
        }
        A[k] = temp;
    }

    void heapSort(vector<int>& A, int len){
        for (int i = len / 2 - 1; i >= 0; i--){
            heap_down(A, i, len);
        }
    }

    void sortIntegers2(vector<int>& A) {
        heapSort(A, A.size());
        for (int i = A.size() - 1; i > 0; i--){
            swap(A[0], A[i]);
            heapSort(A, i);
        }
    }

转载请注明:CodingBlog » 整数排序

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情