快速排序

java

package com.test.arithmetic;

import java.util.Arrays;

/**
 * Two point go together, small is left and big is right.
 * Thus the first meet will separate the array to half small and half big.
 * Created by Ryan on 2017/3/25/025.
 */
public class QuickSort {
    public  int count = 0;

    public  int[] sort(int[] source, int low, int high) {
        if (low >= high) {
            return source;
        }
        int first = low;
        int last = high;
        int key = source[first];

        while (first < last) {
            //find the first smaller from the end
            while (last > first && source[last] >= key) {
                last--;
            }
            if (first < last) {
                source[first] = source[last];
                first++; //The first one has already been sorted, move to the next one.
            }//else first = last, that is the same one, do not need to swap them

            //find the first bigger from the start
            while (first < last && source[first] <= key) {
                first++;
            }

            if (first < last) {
                source[last] = source[first];
                last--; //The last one has already been sorted as a bigger, move to the previous one.
            }

        }

        source[first] = key; //put the key
        System.out.println("The " + ++count + " sort:");
        Arrays.stream(source).forEach(item -> System.out.print(item + ", "));
        System.out.println();

        sort(source, low, first - 1);
        sort(source, first + 1, high);
        return source;

    }



    public void quickSort1(int arr[], int low, int high) {
        int l = low;
        int h = high;
        int key = arr[low];

        while (l < h) {
            while (l < h && arr[h] >= key) {
                h--;
            }

            if (l < h) {
                int temp = arr[h];
                arr[h] = arr[l];
                arr[l] = temp;
                l++;
            }

            while (l < h && arr[l] <= key) {
                l++;
            }


            if (l < h) {
                int temp = arr[h];
                arr[h] = arr[l];
                arr[l] = temp;
                h--;
            }
        }
        System.out.print("l=" + (l + 1) + "h=" + (h + 1) + "key=" + key + "\n");
        if (l > low) quickSort1(arr, low, l - 1);
        if (h < high) quickSort1(arr, l + 1, high);
    }


    public <T> void swap(T[] source, int i, int j) {
        T temp = source[i];
        source[i] = source[j];
        source[j] = temp;
    }

    /**
     * 方式2 更高效点的代码:
     */
    public <T extends Comparable<? super T>> T[] quickSort2(T[] targetArr, int start, int end) {
        int i = start + 1, j = end;
        T key = targetArr[start];

        if (start >= end) return (targetArr);

        /**
         * 从i++和j--两个方向搜索不满足条件的值并交换
         *条件为:i++方向小于key,j--方向大于key
         */
        while (true) {
            while (targetArr[j].compareTo(key) > 0) j--;
            while (targetArr[i].compareTo(key) < 0 && i < j) i++;
            if (i >= j) break;
            this.swap(targetArr, i, j);
            if (targetArr[i] == key) {
                j--;
            } else {
                i++;
            }
        }

        /**
         * 关键数据放到‘中间’*
         */
        this.swap(targetArr, start, j);

        if (start < i - 1) {
            this.quickSort2(targetArr, start, i - 1);
        }
        if (j + 1 < end) {
            this.quickSort2(targetArr, j + 1, end);
        }

        return targetArr;
    }

    /**
     * 方式3:减少交换次数,提高效率
     */
    public  <T extends Comparable<? super T>> void quickSort3(T[] targetArr, int start, int end) {
        int i = start, j = end;
        T key = targetArr[start];

        while (i < j) {
                /*按j--方向遍历目标数组,直到比key小的值为止*/
            while (j > i && targetArr[j].compareTo(key) >= 0) {
                j--;
            }
            if (i < j) {
                    /*targetArr[i]已经保存在key中,可将后面的数填入*/
                targetArr[i] = targetArr[j];
                i++;
            }
                /*按i++方向遍历目标数组,直到比key大的值为止*/
                /*此处一定要小于等于零,假设数组之内有一亿个1,0交替出现的话,而key的值又恰巧是1的话,那么这个小于等于的作用就会使下面的if语句少执行一亿次。*/
            while (i < j && targetArr[i].compareTo(key) <= 0) {
                i++;
            }
            if (i < j) {
                    /*targetArr[j]已保存在targetArr[i]中,可将前面的值填入*/
                targetArr[j] = targetArr[i];
                j--;
            }
                /*此时i==j*/
            targetArr[i] = key;

                /*递归调用,把key前面的完成排序*/
            this.quickSort3(targetArr, start, i - 1);

                /*递归调用,把key后面的完成排序*/
            this.quickSort3(targetArr, j + 1, end);
        }
    }


}

Test:

package com.test.arithmetic;

import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

import java.util.Arrays;

import static org.junit.Assert.*;

/**
 * Created by Ryan on 2017/3/25/025.
 */
public class QuickSortTest {
    private int[] source;
    private Integer[] source2;
    private Integer[] source3;
    private QuickSort quick;

    private int[] expect;
    private Integer[] expect2;
    private Integer[] expect3;

    @Before
    public void setUp(){
        source = new int[]{13, 16, 1, 1, 5, 15, 13, 15, 13, 8};
        source2 = new Integer[]{13, 16, 1, 1, 5, 15, 13, 15, 13, 8};
        source3 = new Integer[]{13, 16, 1, 1, 5, 15, 13, 15, 13, 8};

        expect = new int[]{1, 1, 5, 8, 13, 13, 13, 15, 15, 16};
        expect2 = new Integer[]{1, 1, 5, 8, 13, 13, 13, 15, 15, 16};
        expect3 = new Integer[]{1, 1, 5, 8, 13, 13, 13, 15, 15, 16};
        quick = new QuickSort();
    }


    @Test
    public void testSort() throws Exception {
        int[] source = new int[]{13,16,1,1,5,15,13,15,13,8 };
        int[] sort = quick.sort(source, 0, source.length - 1);
        Assert.assertArrayEquals(expect, sort);
    }
    @Test
    public void testSort1(){
        QuickSort quick = new QuickSort();
        quick.quickSort1(source, 0, source.length - 1);
        Assert.assertArrayEquals(expect, source);
    }

    @Test
    public void testSort2(){
        QuickSort quick = new QuickSort();
        quick.quickSort2(source2, 0, source2.length - 1);
        Assert.assertArrayEquals(expect2, source2);
    }
    @Test
    public void testSort3(){
        QuickSort quick = new QuickSort();
        quick.quickSort3(source3, 0, source.length - 1);
        Assert.assertArrayEquals(expect3, source3);
    }

}

Result:

l=5h=5key=13
l=4h=4key=8
l=1h=1key=1
l=3h=3key=5
l=2h=2key=1
l=9h=9key=15
l=6h=6key=13
l=7h=7key=13
l=8h=8key=15
l=10h=10key=16
The 1 sort:
8, 5, 1, 1, 13, 15, 13, 15, 13, 16, 
The 2 sort:
1, 5, 1, 8, 13, 15, 13, 15, 13, 16, 
The 3 sort:
1, 5, 1, 8, 13, 15, 13, 15, 13, 16, 
The 4 sort:
1, 1, 5, 8, 13, 15, 13, 15, 13, 16, 
The 5 sort:
1, 1, 5, 8, 13, 13, 13, 15, 15, 16, 
The 6 sort:
1, 1, 5, 8, 13, 13, 13, 15, 15, 16, 
The 7 sort:
1, 1, 5, 8, 13, 13, 13, 15, 15, 16, 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏疯狂的小程序

微信小程序版2048小游戏(附源码)

最近流行微信“跳一跳”小游戏,我也心血来潮写了一个微信小程序版2048,本篇文章主要分享实现2048的算法以及注意的点,一起来学习吧!(源码地址见文章末尾)

1K8
来自专栏Android知识点总结

开源计划之--Android绘图库--LogicCanvas

Painter采用单例模式 优化原型模式,各Shape采用深拷贝来解决构造较长、繁琐的情况 比较new 对象和拷贝的效率问题,拷贝一点。具体见文:来谈谈Ja...

673
来自专栏Petrichor的专栏

命名法 的 简洁归纳表

704
来自专栏前端布道

操作数组不要只会for循环

很多时候,我们在操作数组的时候往往就是一个for循环干到底,对数组提供的其它方法视而不见。看完本文,希望你可以换种思路处理数组,然后可以写出更加漂亮、简洁、函数...

2849
来自专栏GIS讲堂

Arcgis for JavaSctipt之常用Layer详解

概述:Arcgis for Javasctipt中常见的layer有动态图层(ArcGISDynamicMapServiceLayer

1005
来自专栏GopherCoder

charts: 图表工具

2063
来自专栏Felix的技术分享

LeetCode第13题--Roman to Integer(Java实现)

1363
来自专栏跟着阿笨一起玩NET

asp.net中的比较完美的验证码

本文转载:http://blog.csdn.net/zjk20108023/article/details/7836174

471
来自专栏SeanCheney的专栏

《Pandas Cookbook》第04章 选取数据子集1. 选取Series数据2. 选取DataFrame的行3. 同时选取DataFrame的行和列4. 用整数和标签选取数据5. 快速选取标量6

第01章 Pandas基础 第02章 DataFrame运算 第03章 数据分析入门 第04章 选取数据子集 第05章 布尔索引 第06章 索引对齐 ...

321
来自专栏练小习的专栏

The Cat and the Hat CSS Selectors

One of the trickier aspects of encapsulating Shadow DOM CSS is figuring out how ...

1907

扫码关注云+社区