Java教程

十大排序算法

本文主要是介绍十大排序算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1. 十大排序算法

其中 冒泡,选择,归并,快速,希尔,堆排序属于比较排序

20210130002554

稳定性理解

如果相等的两个元素,在排序前后的相对位置保持不变,那么这是稳定的排序算法。

  • 排序前:5,1,3(a),4,7,3(b)

  • 稳定的排序:1,3(a),3(b),4,5,7

  • 不稳定的排序:1,3(b),3(a),4,5,7

原地算法(In-place Algorithm)理解

定义:不依赖额外的资源或依赖少数的额外资源(空间复杂度较低),仅依靠输出覆盖输入(例如直接对输入的数组进行操作)

2. 工具类

用于提供测试数据与测试代码正确性

2.1 断言工具类

public class Asserts {
   public static void test(boolean value) {
      try {
         if (!value) throw new Exception("测试未通过");
      } catch (Exception e) {
         e.printStackTrace();
      }
   }
}

2.2 Integers工具类

public class Integers {
	/** 生成随机数 */
	public static Integer[] random(int count, int min, int max) {
		if (count <= 0 || min > max) return null;
		Integer[] array = new Integer[count];
		int delta = max - min + 1;
		for (int i = 0; i < count; i++) {
			array[i] = min + (int)(Math.random() * delta);
		}
		return array;
	}

	/** 合并两个数组 */
	public static Integer[] combine(Integer[] array1, Integer[] array2) {
		if (array1 == null || array2 == null) return null;
		Integer[] array = new Integer[array1.length + array2.length];
		for (int i = 0; i < array1.length; i++) {
			array[i] = array1[i];
		}
		for (int i = 0; i < array2.length; i++) {
			array[i + array1.length] = array2[i];
		}
		return array;
		
	}

	public static Integer[] same(int count, int unsameCount) {
		if (count <= 0 || unsameCount > count) return null;
		Integer[] array = new Integer[count];
		for (int i = 0; i < unsameCount; i++) {
			array[i] = unsameCount - i;
		}
		for (int i = unsameCount; i < count; i++) {
			array[i] = unsameCount + 1;
		}
		return array;
	}

	/**
	 * 生成头部和尾部是升序的数组
	 * disorderCount:希望多少个数据是无序的
	 */
	public static Integer[] headTailAscOrder(int min, int max, int disorderCount) {
		Integer[] array = ascOrder(min, max);
		if (disorderCount > array.length) return array;
		
		int begin = (array.length - disorderCount) >> 1;
		reverse(array, begin, begin + disorderCount);
		return array;
	}

	/**
	 * 生成中间是升序的数组
	 * disorderCount:希望多少个数据是无序的
	 */
	public static Integer[] centerAscOrder(int min, int max, int disorderCount) {
		Integer[] array = ascOrder(min, max);
		if (disorderCount > array.length) return array;
		int left = disorderCount >> 1;
		reverse(array, 0, left);
		
		int right = disorderCount - left;
		reverse(array, array.length - right, array.length);
		return array;
	}

	/**
	 * 生成头部是升序的数组
	 * disorderCount:希望多少个数据是无序的
	 */
	public static Integer[] headAscOrder(int min, int max, int disorderCount) {
		Integer[] array = ascOrder(min, max);
		if (disorderCount > array.length) return array;
		reverse(array, array.length - disorderCount, array.length);
		return array;
	}

	/**
	 * 生成尾部是升序的数组
	 * disorderCount:希望多少个数据是无序的
	 */
	public static Integer[] tailAscOrder(int min, int max, int disorderCount) {
		Integer[] array = ascOrder(min, max);
		if (disorderCount > array.length) return array;
		reverse(array, 0, disorderCount);
		return array;
	}

	/** 升序生成数组 */
	public static Integer[] ascOrder(int min, int max) {
		if (min > max) return null;
		Integer[] array = new Integer[max - min + 1];
		for (int i = 0; i < array.length; i++) {
			array[i] = min++;
		}
		return array;
	}

	/** 降序生成数组 */
	public static Integer[] descOrder(int min, int max) {
		if (min > max) return null;
		Integer[] array = new Integer[max - min + 1];
		for (int i = 0; i < array.length; i++) {
			array[i] = max--;
		}
		return array;
	}
	
	/** 反转数组 */
	private static void reverse(Integer[] array, int begin, int end) {
		int count = (end - begin) >> 1;
		int sum = begin + end - 1;
		for (int i = begin; i < begin + count; i++) {
			int j = sum - i;
			int tmp = array[i];
			array[i] = array[j];
			array[j] = tmp;
		}
	}

	/** 复制数组 */
	public static Integer[] copy(Integer[] array) {
		return Arrays.copyOf(array, array.length);
	}

	/** 判断数组是否升序 */
	public static boolean isAscOrder(Integer[] array) {
		if (array == null || array.length == 0) return false;
		for (int i = 1; i < array.length; i++) {
			if (array[i - 1] > array[i]) return false;
		}
		return true;
	}

	/** 打印数组 */
	public static void println(Integer[] array) {
		if (array == null) return;
		StringBuilder string = new StringBuilder();
		for (int i = 0; i < array.length; i++) {
			if (i != 0) string.append("_");
			string.append(array[i]);
		}
		System.out.println(string);
	}
}

2.3 时间测试工具类

public class Times {
	private static final SimpleDateFormat fmt = new SimpleDateFormat("HH:mm:ss.SSS");
	
	public interface Task {
		void execute();
	}
	
	public static void test(String title, Task task) {
		if (task == null) return;
		title = (title == null) ? "" : ("【" + title + "】");
		System.out.println(title);
		System.out.println("开始:" + fmt.format(new Date()));
		long begin = System.currentTimeMillis();
		task.execute();
		long end = System.currentTimeMillis();
		System.out.println("结束:" + fmt.format(new Date()));
		double delta = (end - begin) / 1000.0;
		System.out.println("耗时:" + delta + "秒");
		System.out.println("-------------------------------------");
	}
}

2.4 Sort抽象父类

public abstract class Sort<T extends Comparable<T>> implements Comparable<Sort<T>> {
    /** 目标数组 */
    protected T[] array;
    /** 比较次数 */
    private int cmpCount;
    /** 交换次数 */
    private int swapCount;
    /** 执行时间 */
    private long time;
    /** 小数格式化 */
    private DecimalFormat fmt = new DecimalFormat("#.00");

    /** 预处理 */
    public void sort(T[] array) {
        if (array == null || array.length < 2) return;
        this.array = array;
        long begin = System.currentTimeMillis();
        sort();
        time = System.currentTimeMillis() - begin;
    }

    /** 目标方法 */
    protected abstract void sort();

    /**
     * 比较数组下标对应的值
     *
     * 返回值等于0,代表 array[index1] == array[index2]
     * 返回值小于0,代表 array[index1] < array[index2]
     * 返回值大于0,代表 array[index1] > array[index2]
     */
    protected int cmp(int index1, int index2) {
        cmpCount++;
        return array[index1].compareTo(array[index2]);
    }

    /** 比较值 */
    protected int cmp(T value1, T value2) {
        cmpCount++;
        return value1.compareTo(value2);
    }

    /** 交换值 */
    protected void swap(int index1, int index2) {
        swapCount++;
        T tmp = array[index1];
        array[index1] = array[index2];
        array[index2] = tmp;
    }

    /** 稳定性测试 */
    @SuppressWarnings("unchecked")
    private boolean isStable() {
        Student[] students = new Sort.Student[20];
        for (int i = 0; i < students.length; i++) {
            //(0,10) (10,10) (20,10) (30,10)
            students[i] = new Student(i * 10, 10);
        }
        sort((T[]) students);//只会对年龄进行排序
        for (int i = 1; i < students.length; i++) {
            int score = students[i].score;
            int prevScore = students[i - 1].score;
            if (score != prevScore + 10) return false;
        }
        return true;
    }

    private static class Student implements Comparable<Student>{
        Integer score;
        Integer age;
        public Student(Integer score, Integer age) {
            this.score = score;
            this.age = age;
        }

        @Override
        public int compareTo(Student o) {
            return age - o.age;
        }
    }

    /** 排序方式 */
    @Override
    public int compareTo(Sort o) {
        int result = (int)(time - o.time);
        if(result != 0) return result;
        result = cmpCount - o.cmpCount;
        if(result != 0) return result;
        return swapCount - o.swapCount;
    }

    @Override
    public String toString() {
        return "【" + getClass().getSimpleName() + "】\n"
                + "交换次数 ==> " + numberString(swapCount) + "\n"
                + "比较次数 ==> " + numberString(cmpCount) + "\n"
                + "执行时间 ==> " + time * 0.001 + "s" + "\n"
                + "稳定性 ==> " + isStable() + "\n"
                + "=================================";
    }

    /** 数字格式化 */
    private String numberString(int number) {
        if (number < 10000) return "" + number;

        if (number < 100000000) {
            return fmt.format(number / 10000.0) + "万";
        }
        return fmt.format(number / 100000000.0) + "亿";
    }

}

3. 冒泡排序(Bubble Sort)

3.1 执行流程

  • 从头开始比较每一对相邻元素,如果第一个比第二个大就交换它们的位置。执行完一轮后最末尾哪个元素就是最大的元素
  • 忽略第一步找到的最大元素,重复执行第一步,直到全部元素有序
BubbleSort

3.2 基本实现

public void sort() {
    for (int eIndex = array.length - 1; eIndex > 0; eIndex--) {
        for (int i = 1; i <= eIndex; i++) {
            if (cmp(i, i - 1) < 0) {
                swap(i, i - 1);
            }
        }
    }
}

3.4 优化一

优化方案:如果序列已经完全有序,可以提前终止冒泡排序

缺点:只有当完全有序时才会提前终止冒泡排序,概率很低

public void sort() {
    for (int eIndex = array.length - 1; eIndex > 0; eIndex--) {
        boolean sorted = true;
        for (int i = 1; i <= eIndex; i++) {
            if (cmp(i,i - 1) < 0) {
                swap(i, i - 1);
                sorted = false;
            }
        }
        if (sorted) break;
    }
}

3.5 优化二

优化方案:如果序列尾部已经局部有序,可以记录最后一次交换的位置,减少比较次数

20210130011659
public class BubbleSort<T extends Comparable<T>> extends Sort<T> {
    /**
     *  优化方式二:如果序列尾部已经局部有序,可以记录最后依次交换的位置,减少比较次数
     *  为什么这里sortedIndex为1(只要保证 eIndex-- > 0 即可)?
     *     => 如果sortedIndex为eIndex,当数组第一次就完全有序时,就退回到最初的版本了
     *     => 如果sortedIndex为1,当数组第一次就完全有序时,一轮扫描就结束了!
     * 
     */
    @Override
    public void sort() {
        for (int eIndex = array.length - 1; eIndex > 0; eIndex--) {
            int sortedIndex = 1; //记录最后一次交换的下标位置
            for (int i = 1; i <= eIndex; i++) {
                if (cmp(i, i - 1) < 0) {
                    swap(i, i - 1);
                    sortedIndex = i;
                }
            }
            eIndex = sortedIndex;
        }
    }
}

3.6 算法优劣

  • 最坏,平均时间复杂度:O(n^2),最好时间复杂度:O(n)

  • 空间复杂度:O(1)

  • 属于稳定排序

注意:稍有不慎,稳定的排序算法也能被写成不稳定的排序算法,如下冒泡排序是不稳定的

public void sort() {
    for (int eIndex = array.length - 1; eIndex > 0; eIndex--) {
        for (int i = 1; i <= eIndex; i++) {
            if (cmp(i, i - 1) <= 0) {
                swap(i, i - 1);
            }
        }
    }
}
  • 属于原地算法

4. 选择排序(Selection Sort)

4.1 执行流程

  • 从序列中找出最大的哪个元素,然后与最末尾的元素交换位置。执行完一轮后最末尾那个元素就是最大的元素
  • 忽略第一步找到的最大元素,重复执行第一步

这里以选最小元素为例

SelectionSort

4.2 基本实现

public class SelectionSort<T extends Comparable<T>> extends Sort<T> {
    @Override
    public void sort() {
        for (int eIndex = array.length - 1; eIndex > 0; eIndex--) {
            int maxIndex = 0;
            for (int i = 1; i <= eIndex; i++) {
                //注意:为了稳定性,这里要写 <=
                if (cmp(maxIndex, i) <= 0) {
                    maxIndex = i;
                }
            }
            if(maxIndex != eIndex) swap(maxIndex, eIndex);
        }
    }

}

4.3 算法优劣

  • 选择排序的交换次数要远少于冒泡排序,平均性能优于冒泡排序
  • 最好,最坏,平均时间复杂度均为O(n^2),空间复杂度为O(1),属于不稳定排序

选择排序是否还有优化的空间? => 使用堆来选择最大值

5. 堆排序(Heap Sort)

堆排序可以认为是对选择排序的一种优化

5.1 执行流程

  • 对序列进行原地建堆(heapify)
  • 重复执行以下操作,直到堆的元素数量为1
    • 交换堆顶元素与尾元素
    • 堆的元素数量减1
    • 对0位置进行一次siftDown操作
image-20210130235449796

5.2 基本实现

public class HeapSort<T extends Comparable<T>> extends Sort<T> {
    /** 记录堆数据 */
    private int heapSize;

    @Override
    protected void sort() {
        // 原地建堆(直接使用数组建堆)
        heapSize = array.length;
        for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }
        while (heapSize > 1) {
            // 交换堆顶元素和尾部元素
            swap(0, --heapSize);

            // 对0位置进行siftDown(恢复堆的性质)
            siftDown(0);
        }
    }

    /** 堆化 */
    private void siftDown(int index) {
        T element = array[index];

        int half = heapSize >> 1;
        while (index < half) { // index必须是非叶子节点
            // 默认是左边跟父节点比
            int childIndex = (index << 1) + 1;
            T child = array[childIndex];

            int rightIndex = childIndex + 1;
            // 右子节点比左子节点大
            if (rightIndex < heapSize &&
                    cmp(array[rightIndex], child) > 0) {
                child = array[childIndex = rightIndex];
            }

            // 大于等于子节点
            if (cmp(element, child) >= 0) break;

            array[index] = child;
            index = childIndex;
        }
        array[index] = element;
    }
}

5.2 算法优劣

  • 最好,最坏,平均时间复杂度:O(nlog^n)

  • 空间复杂度:O(1)

  • 属于不稳定排序

5.3. 冒泡,选择,堆排序比较

@SuppressWarnings({"rawtypes","unchecked"})
public class SortTest {
    public static void main(String[] args) {
        Integer[] arr1 = Integers.random(10000, 1, 20000);
        testSort(arr1,
                new SelectionSort(),
                new HeapSort(),
                new BubbleSort());

    }

    static void testSort(Integer[] arr,Sort... sorts) {
        for (Sort sort: sorts) {
            Integer[] newArr = Integers.copy(arr);
            sort.sort(newArr);
            //检查排序正确性
            Asserts.test(Integers.isAscOrder(newArr));
        }
        Arrays.sort(sorts);
        for (Sort sort: sorts) {
            System.out.println(sort);
        }
    }
}
image-20210130235941183

6. 插入排序(Insertion Sort)

6.1 执行流程

  • 在执行过程中,插入排序会将序列分为两部分(头部是已经排好序的,尾部是待排序的)

  • 从头开始扫描每一个元素,每当扫描到一个元素,就将它插入到头部适合的位置,使得头部数据依然保持有序

InsertionSort

6.2 基本实现

public class InsertionSort<T extends Comparable<T>> extends Sort<T> {
    @Override
    protected void sort() {
        for (int i = 1; i < array.length; i++) {
            int cur = i;
            while(cur > 0 && cmp(cur,cur - 1) < 0) {
                swap(cur,cur - 1);
                cur--;
            }
        }
    }
}

6.3 逆序对(Inversion)

什么是逆序对? => 数组 [2,3,8,6,1] 的逆序对为:<2,1> < 3,1> <8,1> <8,6> <6,1>

插入排序的时间复杂度与逆序对的数量成正比关系

时间复杂度最高如下:O(n^2)

image-20210131010515436

6.4 优化一

优化思路 => 将交换改为挪动

  • 先将待插入元素备份

  • 头部有序数据中比待插入元素大的,都朝尾部方向挪动1个位置

  • 将待插入元素放到最终合适位置

注意:逆序对越多,该优化越明显

image-20210131012202402
public class InsertionSort<T extends Comparable<T>> extends Sort<T> {
    @Override
    protected void sort() {
        for (int i = 1; i < array.length; i++) {
            int cur = i;
            T val = array[cur];
            while(cur > 0 && cmp(val,array[cur - 1]) < 0) {
                array[cur] = array[cur - 1];//优化重点在这里
                cur--;
            }
            array[cur] = val;
        }
    }
}

6.5 优化二

优化思路 => 将交换改为二分搜索(较少比较次数)

二分搜索理解

如何确定一个元素在数组中的位置?(假设数组里全是整数)

  • 如果是无序数组,从第 0 个位置开始遍历搜索,平均时间复杂度:O(n)

  • 如果是有序数组,可以使用二分搜索,最坏时间复杂度:O(log^n)

思路

  • 如下,假设在 [begin, end) 范围内搜索某个元素 v,mid == (begin + end) / 2
  • 如果 v < mid,去 [begin,mid) 范围内二分搜索
  • 如果 v > mid,去 [mid + 1,end) 范围内二分搜索
  • 如果 v == mid,直接返回 mid
image-20210131214722123

实例

image-20210131215305715
/** 二分搜索-基本实现
 *      查找val在有序数组arr中的位置,找不到就返回-1
 */
private static int indexOf(Integer[] arr,int val) {
    if(arr == null || arr.length == 0) return -1;
    int begin = 0;
    //注意这里end设计为arr.length便于求数量(end - begin)
    int end = arr.length;
    while (begin < end) {
        int mid = (begin + end) >> 1;
        if(val < arr[mid]) {
            end = mid;
        } else if(val > arr[mid]) {
            begin = mid  + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

二分搜索(Binary Search)优化实现

  • 之前的插入排序代码,在元素 val 的插入过程中,可以先二分搜索出合适的插入位置,然后将元素 val 插入
  • 适合于插入排序的二分搜索必须满足:要求二分搜索返回的插入位置是第1个大于 val 的元素位置
    • 如果 val 是 5 ,返回 2
    • 如果 val 是 1,返回 0
    • 如果 val 是15,返回 7
    • 如果 val 是 8,返回 5
image-20210131221938281
  • 实现思路
    • 假设在 [begin,end) 范围内搜索某个元素 val,mid == (begin + end) / 2
    • 如果val < mid,去 [begin,mid) 范围内二分搜索
    • 如果val >= mid,去 [mid + 1,end) 范围内二分搜索
    • 当 begin == end == x,x 就是待插入位置
  • 实例
image-20210131224559325
/**
 * 二分搜索-适用于插入排序
 *    查找val在有序数组arr中可以插入的位置
 *    规定:要求二分搜索返回的插入位置是第1个大于 val 的元素位置
 */
private static int search(Integer[] arr,int val) {
    if(arr == null || arr.length == 0) return -1;
    int begin = 0;
    int end = arr.length;
    while (begin < end) {
        int mid = (begin + end) >> 1;
        if(val < arr[mid]) {
            end = mid;
        } else {
            begin = mid  + 1;
        }
    }
    return begin;
}

插入排序最终实现

注意:使用了二分搜索后,只是减少了比较次数,但插入排序的平均时间复杂度依然是O(n^2)

public class InsertionSort<T extends Comparable<T>> extends Sort<T> {
 
    /** 优化 => 二分搜索 */
    @Override
    protected void sort() {
        for (int begin = 1; begin < array.length; begin++) {
            //这里为什么传索引而不是传值?
            // => 传索引还可以知道前面已经排好序的数组区间:[0,i)
            insert(begin,search(begin));
        }
     }

    /** 将source位置的元素插入到dest位置 */
    private void insert(int source,int dest) {
         //将[dest,source)范围内的元素往右边挪动一位
         T val = array[source];
         for (int i = source; i > dest; i--) {
             array[i] = array[i - 1];
         }
         //插入
         array[dest] = val;
    }

    private int search(int index) {
        T val = array[index];
        int begin = 0;
        int end = index;
        while (begin < end) {
            int mid = (begin + end) >> 1;
            if(cmp(val,array[mid]) < 0) {
                end = mid;
            } else {
                begin = mid  + 1;
            }
        }
        return begin;
    }
}

6.6 算法优劣

image-20210131231517195
  • 最坏,平均时间复杂度为 O(n^2),最好时间复杂度为 O(n)
  • 空间复杂度为 O(1)
  • 属于稳定排序

7. 归并排序(Merge Sort)

7.1 执行流程

  • 不断的将当前序列平均分割成 2 个子序列,直到不能再分割(序列中只剩一个元素)
  • 不断的将 2 个子序列合并成一个有序序列,直到最终只剩下 1 个有序序列

MergeSortimage-20210131234043161

7.2 思路

merge

大致想法

image-20210201001248209

细节

  • 需要 merge 的 2 组序列存在于同一个数组中,并且是挨在一起的
image-20210201001738365
  • 为了更好的完成 merge 操作,最好将其中 1 组序列备份出来,比如 [begin,mid)
image-20210201002214497
  • 基本实现
image-20210201002810524
  • 情况一:左边先结束 => 左边一结束整个归并就结束
image-20210201003223422
  • 情况二:右边先结束 => 右边一结束就直接将左边按顺序挪到右边去
image-20210201003620035

7.3 基本实现

@SuppressWarnings("unchecked")public class MergeSort<T extends Comparable<T>> extends Sort<T> {    private T[] leftArr;    @Override    protected void sort() {        leftArr = (T[]) new Comparable[array.length >> 1];        sort(0, array.length);    }    /** 对 [begin,end) 位置的元素进行归并排序 */    private void sort(int begin, int end) {        if (end - begin < 2) return;        int mid = (begin + end) >> 1;        sort(begin, mid);        sort(mid, end);        merge(begin, mid, end);    }    /** 将 [begin,mid) 和 [mid,end) 范围的序列合并成一个有序序列 */    private void merge(int begin, int mid, int end) {        int li = 0, le = mid - begin;        int ri = mid, re = end;        int ai = begin;        //备份左边数组        for (int i = 0; i < le; i++) {            leftArr[i] = array[begin + i];        }        //如果左边还没有结束(情况一)        while (li < le) {            //当 ri < re 不成立,就会一直leftArr挪动(情况二)            if (ri < re && cmp(array[ri],leftArr[li]) < 0) {                array[ai++] = array[ri++];            } else { //注意稳定性                array[ai++] = leftArr[li++];            }        }    }}

7.4 算法优劣

image-20210201013107391

复杂度分析

T(n) = sort() + sort() + merge()=> T(n) = T(n/2) + T(n/2) + O(n)=>  T(n) = 2T(n/2) + O(n)    //由于sort()是递归调用,用T表示,由于T(n/2)不好估算,现在要理清T(n)与O(n)之间的关系T(1) = O(1)T(n)/n = T(n/2) / (n/2) + O(1)    //令S(n) = T(n)/n     S(1) = O(1) S(n) = S(n/2) + O(1)      = S(n/4) + O(2)     = S(n/8) + O(3)     = S( n/(2^k) ) + O(k)     = S(1) + O(log^n)     = O(lon^n)T(n) = n*S(n) = O(nlog^n)    => 归并排序时间复杂度:O(nlog^n)

常见递推式

image-20210201013429126

总结

  • 由于归并排序总是平均分割子序列,所以最好,最坏,平均时间复杂度都是:O(nlog^n)

  • 空间复杂度:O(n/2 + log^n) = O(n),n/2用于临时存放左侧数组,log^n用于递归调用

  • 属于稳定排序

这篇关于十大排序算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!