快速排序

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 条评论
登录 后参与评论

相关文章

来自专栏杨龙飞前端

leetCode刷题(找到最长的连续不重复的字符串长度)

1664
来自专栏恰同学骚年

剑指Offer面试题:3.替换空格

  在网络编程中,如果URL参数中含有特殊字符,如空格、'#'等,可能导致服务器端无法获得正确的参数值。我们需要将这些特殊符号转换成服务器可以识别的字符。转换的...

562
来自专栏菩提树下的杨过

javascript中定义私有方法(private method)

一度以为在javascript的世界里,所有方法都是公有的,无法真正从技术上定义一个私有方法,今天又一次发现:其实我错了!  var Person = func...

1817
来自专栏mathor

堆及其相关应用

 提到堆就不得不说到二叉树这个结构,堆就是一颗完全二叉树,什么叫完全二叉树,用一句话来概括就是:设二叉树的深度为h,除第h层外,其它各层的结点数都达到最大个数,...

732
来自专栏nnngu

算法01 七大排序之:冒泡排序和快速排序

排序是我们生活中经常会面对的问题。同学们做操时会按照从矮到高排列;老师查看上课出勤情况时,会按学生学号顺序点名;高考录取时,会按成绩总分降序依次录取等。排序是数...

3527
来自专栏PHP实战技术

解构赋值,你不能不懂!

13210
来自专栏恰同学骚年

数据结构基础温故-7.排序

排序(Sorting)是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为按关键字“有序”的记录序列。如何进行排序,特别是高效率地进行排序时计算...

511
来自专栏JetpropelledSnake

Python入门之面向对象的多态和继承

本章内容     Python面向对象的多态和继承对比 ========================================= 在OOP程序设计中,...

2734
来自专栏小樱的经验随笔

【Java学习笔记之十一】Java中常用的8大排序算法详解总结

分类: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(基...

2806
来自专栏和蔼的张星的图像处理专栏

算法1.排序二分查找及其变种

这个我也不知道能写多少,只是最近快放假了实在懒得看DSP了,而且卡在一个地方了,什么都不干又感觉心慌的很,所以又回头看看算法的东西。一些测试程序放在这里

722

扫描关注云+社区