八大排序算法的Java实现（上）

概述

排序有内部排序和外部排序

• 内部排序是数据记录在内存中进行排序
• 外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存

时间复杂度为最差情况下的复杂度

八大排序就是内部排序

当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快排,堆排,归排

快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短

稳定性:在值相等情况下,相对次序保持不变

#1. 插入排序—直接插入排序(Straight Insertion Sort)

• 基本思想: 将一个记录插入到已排序好的有序表中，从而得到一个新且记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

• 要点 设立哨兵，作为临时存储和判断数组边界之用。

• 直接插入排序示例

元素相等的，把欲插入的元素放在相等元素的后面 所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序 所以插入排序稳定

• 实现：

public class InsertionSort { public static void insertionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 1; i < arr.length; i++) { for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) { swap(arr, j, j + 1); } } } public static void swap(int[] arr, int i, int j) { arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; } // for test public static void comparator(int[] arr) { Arrays.sort(arr); } // for test public static int[] generateRandomArray(int maxSize, int maxValue) { int[] arr = new int[(int) ((maxSize + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr; } // for test public static int[] copyArray(int[] arr) { if (arr == null) { return null; } int[] res = new int[arr.length]; for (int i = 0; i < arr.length; i++) { res[i] = arr[i]; } return res; } // for test public static boolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) { return false; } if (arr1 == null && arr2 == null) { return true; } if (arr1.length != arr2.length) { return false; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] != arr2[i]) { return false; } } return true; } // for test public static void printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // for test public static void main(String[] args) { int testTime = 500000; int maxSize = 100; int maxValue = 100; boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = copyArray(arr1); insertionSort(arr1); comparator(arr2); if (!isEqual(arr1, arr2)) { succeed = false; break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!"); int[] arr = generateRandomArray(maxSize, maxValue); printArray(arr); insertionSort(arr); printArray(arr); } } 

c++版本

void InsertSort(int a[], int n)  
{  
    for(int i= 1; i