本文集将用 java 语言实现包括插入排序(直接插入、折半插入、希尔排序),交换排序(快速排序和冒泡排序),选择排序,堆排序,归并排序以及基数排序在内的所有内排序算法。虽然都很简单且实际开发几乎已运用不到(Arrays.Sort 和 Collection.Sort 可直接调用),但是这些属于一个程序员的基本功,熟稔掌握是必须的。
直接插入排序的思想就是当发现序列不是有序的情况下时,将待排序元素插入到前面已经有序的序列中。所以怎么插是核心问题,其实归根结底还是找到待排序元素的插入位置。由于是从小到大排序,可由待排序元素的前一个位置开始从后向前比较,若发现比较元素大于待排序元素,则将比较元素向后移位以腾出位置。最终将元素赋值给排序结束腾出的位置。
边比较边移位是其特点,所以有待优化的地方。后续的折半插入和希尔排序都是对直接插入排序的一种优化。时间复杂度为 o(n*n)。
以序列 4 3 1 2 5 为例
示例
- package com.fairy.InnerSort;
- import java.util.Scanner;
- /**
- * 直接插入排序
- * @author Fairy2016
- *
- */
- public class DirectInsertSort {
- public static void sort(int a[], int n) {
- int i,
- j;
- for (i = 2; i <= n; i++) {
- if (a[i - 1] > a[i]) {
- a[0] = a[i]; //a[0]作为探针,既存储待排序元素又作循环停止标志,省却if判断
- for (j = i - 1; a[j] > a[0]; j--) {
- a[j + 1] = a[j]; //遇到比a[i]大的向后移位,腾出位置
- }
- a[j + 1] = a[0]; //将待排序元素赋值到最终位置
- }
- }
- }
- public static void Print(int a[], int n) {
- for (int i = 1; i <= n; i++) {
- System.out.print(a[i] + " ");
- }
- }
- public static void main(String args[]) {
- int n;
- int a[];
- Scanner scanner = new Scanner(System. in );
- while (scanner.hasNext()) {
- n = scanner.nextInt();
- if (n > 0) {
- a = new int[n + 1];
- for (int i = 1; i <= n; i++) {
- a[i] = scanner.nextInt();
- }
- sort(a, n);
- Print(a, n);
- }
- }
- }
- }
来源: http://www.jianshu.com/p/0aa95d33f597