美文网首页
算法学习-快速排序

算法学习-快速排序

作者: vincentgemini | 来源:发表于2017-11-14 21:40 被阅读0次

    假设要排序的数组是A[0]……A[N-1]。首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。这样数组就被关键数据分成了两部分,用相同的办法将这两部分继续进行快速排序,直到分隔的数据为单个为止。

    值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。

    代码
    void quick_sort(int a[], int left, int right)
    {
        if (left >= right) {
            return;
        }
        int i = left;
        int j = right;
        int t = a[i];
        while (i < j) {
    
            // 从右向左找第一个小于x的数
            while (i < j && a[j] >= x) {
                j--;
            }
            if (i < j) {
                a[i] = a[j];
                i++;
            }
    
            // 从左向右找第一个大于等于x的数
            while (i < j && a[i] < x) {
                i++;
            }
            if (i < j) {
                a[j] = a[i];
                j--;
            }
        }
        a[i] = t;
    
        // 递归调用
        quick_sort(s, left, i - 1);  
        quick_sort(s, i + 1, right);
    }

    相关文章

      网友评论

          本文标题:算法学习-快速排序

          本文链接:https://www.haomeiwen.com/subject/yacqvxtx.html