排序算法一：插入排序(Insertion sort)
最近从网易公开课在看麻省理工学院的公开课《算法导论》，感觉还不错，接下来几篇文章所示学习日记了，不准备对算法细节做过多描述，感兴趣的可以自己去看。
文章分几篇讲经典排序算法，直接上代码，根据结果对算法性能有个直观了解。本篇先说插入排序（insertion sort）。
(一)算法实现
protected void sort(int[] toSort) {
if (toSort.length <= 1) {
return;
}
for (int i = 1; i < toSort.length; i++) {
if (toSort[i] < toSort[i - 1]) {
int j = i;
int temp = toSort[i];
while (j > 0 && temp < toSort[j - 1]) {
toSort[j] = toSort[j - 1];
j--;
}
toSort[j] = temp;
}
}
}
Insertion sort
1）插入排序属于原地排序，节省空间
2）插入排序的时间复杂度是O(n2)
3）插入排序属于比较排序
4）插入排序属于稳定排序算法
（二）算法性能
**************************************************
Number to Sort is:2500
Array to sort is:{665184,192100,475135,171530,869545,506246,640618,543738,91353,493005...}
Cost time of 【InsertionSort】 is(milliseconds):3
Sort result of 【InsertionSort】:{856,985,2432,3792,3910,3915,4423,4516,4653,4780...}
**************************************************
Number to Sort is:25000
Array to sort is:{99880,631403,265087,597224,876665,955084,996547,879081,197806,926881...}
Cost time of 【InsertionSort】 is(milliseconds):267
Sort result of 【InsertionSort】:{14,14,17,83,97,152,179,199,240,299...}
**************************************************
Number to Sort is:250000
Array to sort is:{777293,731773,508229,920721,338608,707195,940,445210,19071,768830...}
Cost time of 【InsertionSort】 is(milliseconds):21,523
Sort result of 【InsertionSort】:{2,7,7,19,19,21,24,29,30,39...}
相关代码：
package com.cnblogs.riyueshiwang.sort;
import java.util.Arrays;
public class InsertionSort extends abstractSort {
@Override
protected void sort(int[] toSort) {
if (toSort.length <= 1) {
return;
}
for (int i = 1; i < toSort.length; i++) {
if (toSort[i] < toSort[i - 1]) {
int j = i;
int temp = toSort[i];
while (j > 0 && temp < toSort[j - 1]) {
toSort[j] = toSort[j - 1];
j--;
}
toSort[j] = temp;
}
}
}
public static void main(String[] args) {
for (int j = 0, n = 2500; j < 3; j++, n = n * 10) {
System.out
.println("**************************************************");
System.out.println("Number to Sort is:" + n);
int[] array = CommonUtils.getRandomIntArray(n, 1000000);
System.out.print("Array to sort is:");
CommonUtils.printIntArray(array);
int[] array1 = Arrays.copyOf(array, n);
new InsertionSort().sortAndprint(array1);
}
}
}
InsertionSort.java
package com.cnblogs.riyueshiwang.sort;
import java.text.MessageFormat;
public abstract class abstractSort {
/**
*
* @param toSort
* array to sort
*/
protected abstract void sort(int[] toSort);
public void sortAndprint(int[] toSort) {
Long begin = System.currentTimeMillis();
sort(toSort);
Long end = System.currentTimeMillis();
System.out.println(MessageFormat.format(
"Cost time of 【{0}】 is(milliseconds):{1}", this.getClass()
.getSimpleName(), (end - begin)));
System.out.print(MessageFormat.format("Sort result of 【{0}】:", this
.getClass().getSimpleName()));
CommonUtils.printIntArray(toSort);
}
}
abstractSort.java
package com.cnblogs.riyueshiwang.sort;
import java.util.Random;
public class CommonUtils {
private static Random random = new Random();
public static void printIntArray(int[] array) {
System.out.print('{');
int length = Math.min(array.length, 10);
for (int i = 0; i < length; i++) {
System.out.print(array[i]);
if (i != length - 1) {
System.out.print(',');
} else {
if (array.length > 10) {
System.out.print("...");
}
System.out.println('}');
}
}
}
public static int[] getRandomIntArray(int size, int maxValue) {
int[] array = new int[size];
for (int i = 0; i < size; i++) {
array[i] = random.nextInt(maxValue);
}
return array;
}
public static void swap(int[] toSort, int i, int j) {
int temp = toSort[i];
toSort[i] = toSort[j];
toSort[j] = temp;
}
}
CommonUtils.java
最新文章
- iOS7 NavigationController 手势问题
- 第一章 Mybtais的两种启动方式
- apue第六章学习总结
- 低功耗蓝牙4.0BLE编程-nrf51822开发(6)-Battery Service
- javascript知识总汇
- 驱动开发 - WDK 调试及 SVN 环境搭建
- Java之路（六） 局部变量作用域最小化
- HDU 1509 Windows Message Queue(队列)
- JS数组及内置对象
- MySQL长短密码
- Unhandled event loop exception GC overhead limit exceeded
- MyEclipse 2014专业版的破解--Windows系统的软件安装
- 交互题[CF1103B Game with modulo、CF1019B The hat、CF896B Ithea Plays With Chtholly]
- 自己手写一个queuelink
- Go语言之高级篇beego框架之controller调用model
- SVN怎么触发Jenkins自动构建
- "garbage at end of line" on Windows 10
- 【Linux】shell编程案例
- Tensorflow线程和队列
- zabbix3.4.7 饼图显示问题