内部排序比较（Java版）
2017-06-21
目录
1 三种基本排序算法
1.1 插入排序
1.2 交换排序（冒泡）
1.3 选择排序（简单）
2 比较
3 补充
3.1 快速排序
3.2 什么是桶排序
3.3 堆排序
1 三种基本排序算法
1.1 插入排序
public static void InsertSort(int[] arrs) {
int j;
int tmp;
for (int i = 1; i < arrs.length; i++) {
tmp = arrs[i];
for (j = i - 1; j >= 0 && tmp < arrs[j]; j--) {
arrs[j + 1] = arrs[j];
}
arrs[j + 1] = tmp;
}
}
1.2 交换排序（冒泡）
public static void BubbleSortS(int[] arrs) {
int tmp;
for (int i = arrs.length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (arrs[j] > arrs[j + 1]) {
tmp = arrs[j];
arrs[j] = arrs[j + 1];
arrs[j + 1] = tmp;
}
}
}
}
1.3 选择排序（简单）
public static void SelectSort(int[] arrs) {
int minIndex;
int tmp;
for (int i = 0; i < arrs.length - 1; i++) {
minIndex = i;
for (int j = i + 1; j < arrs.length; j++) {
if (arrs[minIndex] > arrs[j])
minIndex = j;
}
if (minIndex != i) {
tmp = arrs[minIndex];
arrs[minIndex] = arrs[i];
arrs[i] = tmp;
}
}
}
2 比较
| 排序方法 | 复杂度 | 辅助空间 | 内外循环 | 一次内循环取最大数 | 一次循环交换次数 |
| 插入排序 | O(n2) | 1 | i=1->length-1 j=i-1->0 |
否 | O(1) |
| 冒泡排序 | O(n2) | 1 | i=length-1->1 j=0->i-1 |
是 | O(n) |
| 选择排序 | O(n2) | 2 | i=0->length-1 j=i+1->length-1 |
是 | O(1) |
内部排序（C#）
3 补充
3.1 快速排序
快速排序是对冒泡排序的一种改进。
- 时间复杂度，最坏是O（n2），一般O（nlogn），
- 空间复杂度（递归实现），在一般情况下的空间复杂度为O（logn），在最差的情况下，若每次只完成了一个元素，那么空间复杂度为O（n）
/**
* 快速排序是在冒泡排序的基础上改进而来的，冒泡排序每次只能交换相邻的两个元素，而快速排序是跳跃式的交换，交换的距离很大，因此总的比较和交换次数少了很多，速度也快了不少。
* 时间复杂度，最坏是O（n2），一般O（nlogn）
*/
public class QuickSort
{
public static void main(String[] args)
{
int[] arr=new int[]{1,5,2,3,6,8,4,9,7,5};
QuickSort quickSort=new QuickSort(arr);
quickSort.sort();
quickSort.print();
} private int[] arr;
public QuickSort(int[] arr)
{
this.arr=arr;
} public void sort()
{
quickSort(arr,0,arr.length-1);
} public void quickSort(int[] arr,int begin,int end)
{
if(begin<end)
{
int i = partition(arr, begin, end);
quickSort(arr,begin,i-1);
quickSort(arr,i+1,end);
}
} private int partition(int[] arr, int begin, int end) {
int key=arr[begin];
while(begin<end)
{
while (begin<end&&arr[end]>=key)end--;
if(begin<end) {
arr[begin] = arr[end];
}
while(begin<end&&arr[begin]<=key)begin++;
if(begin<end) {
arr[end] = arr[begin];
}
}
arr[begin]=key;
return begin;
} public void print()
{
for(int value:arr)
System.out.println(value);
}
}
3.2 什么是桶排序
桶排序，也叫作箱排序，是一个排序算法，也是所有排序算法中最快、最简单的排序算法。其中的思想是我们首先需要知道所有待排序元素的范围，然后需要有在这个范围内的同样数量的桶，接着把元素放到对应的桶中，最后按顺序输出。
- 时间复杂度为O（n+m）
- 空间复杂度是O（m），其中m为桶的个数，
/**
* 桶排序，也叫作箱排序，是一个排序算法，也是所有排序算法中最快、最简单的排序算法。
* 其中的思想是我们首先需要知道所有待排序元素的范围，然后需要有在这个范围内的同样数量的桶，接着把元素放到对应的桶中，最后按顺序输出。
* 由于时间复杂度为O（n+m），m为桶容量,如果m比n大太多，则从时间上来说，性能也并不是很好。
*/
public class BucketSort {
public static void main(String[] args)
{
int[] needSortedArr=new int[]{9,2,3,0,3};
BucketSort bucketSort=new BucketSort(10,needSortedArr);
bucketSort.sort();
bucketSort.print();
} private int[] buckets;
private int[] array; public BucketSort(int range,int[] array)
{
this.buckets=new int[range];
this.array=array;
} public void sort()
{
if(array!=null&&array.length!=0)
{
for(int i=0;i<array.length;i++)
{
buckets[array[i]]++;
}
}
} public void print()
{
for(int i=0;i<buckets.length;i++)
{
for(int j=buckets[i];j>0;j--)
System.out.println(i);
}
}
}
3.3 堆排序
堆的定义
我们可以吧这个序列看成一个二叉树，可得， 1）最大堆的根节点最大，2)上层总比下层大
- 时间复杂度是O（logn）
public class HeapSort {
public static void main(String[] args) {
int[] array = { 8, 6, 9, 7, 5, 4, -3, -2, -1, 0, 1, 2, 3 };
System.out.println("Before heap:");
printArray(array);
printHeapTree(array);
System.out.println("build max heap:");
buildMaxHeap(array);
printArray(array);
printHeapTree(array);
heapSort(array);
System.out.println("After heap sort:");
printArray(array);
printHeapTree(array);
}
public static void heapSort(int[] array) {
if (array == null || array.length <= 1) {
return;
}
//建大顶堆
buildMaxHeap(array);
//堆排序
for (int i = array.length - 1; i >= 1; i--) {
exchangeElements(array, 0, i);
maxHeap(array, i, 0);
}
}
private static void buildMaxHeap(int[] array) {
if (array == null || array.length <= 1) {
return;
}
int half = array.length / 2-1;
for (int i = half; i >= 0; i--) {
maxHeap(array, array.length, i);
}
}
//时间复杂度O(logN)
private static void maxHeap(int[] array, int heapSize, int index) {
int left = index * 2 + 1;
int right = index * 2 + 2;
int largest = index;
if (left < heapSize && array[left] > array[index]) {
largest = left;
}
if (right < heapSize && array[right] > array[largest]) {
largest = right;
}
if (index != largest) {
exchangeElements(array, index, largest);
maxHeap(array, heapSize, largest);
}
}
public static void printArray(int[] array) {
System.out.print("{");
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]);
if (i < array.length - 1) {
System.out.print(", ");
}
}
System.out.println("}");
}
private static void printHeapTree(int[] array)
{
for(int i=1;i<array.length;i=i*2)
{
for(int k=i-1;k<2*(i)-1&&k<array.length;k++)
{
System.out.print(array[k]+" ");
}
System.out.println();
}
}
public static void exchangeElements(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
}