排序算法分为内部排序和外部排序，内部排序把 数据 记录放在内存中进行排序，而外部排序因排序的数据量大，内存不能一次容纳全部的排序记录，所以在排序过程中需要访问外存。
冒泡排序（Bubble Sort）是一种简单的排序算法。它重复访问要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。访问数列的工作是重复地进行直到没有再需要交换的数据，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端，像水中的气泡从水底浮到水面。
冒泡排序算法的算法过程如下：
①. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
②. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
③. 针对所有的元素重复以上的步骤，除了最后一个。
④. 持续每次对越来越少的元素重复上面的步骤①~③，直到没有任何一对数字需要比较。
package com.bobo.dataStructure.sort;
import com.bobo.dataStructure.util.ArrayUtil;
public class BubbleSort implements BaseSort {
public static void main(String[] args) {
int[] array = {5, 4, 3, 2, 1};
BaseSort baseSort = new BubbleSort();
baseSort.sort(array);
}
/**
* 冒泡排序算法的算法过程如下：
* <p>
* ①. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
* <p>
* ②. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
* <p>
* ③. 针对所有的元素重复以上的步骤，除了最后一个。
* <p>
* ④. 持续每次对越来越少的元素重复上面的步骤①~③，直到没有任何一对数字需要比较。
*
* @param array
*/
@Override
public void sort(int[] array) {
if (array.length == 0) {
return;
}
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - 1; j++) {
// 交换
if (array[j + 1] < array[j]) {
int flag = array[j];
array[j] = array[j + 1];
array[j + 1] = flag;
ArrayUtil.printArray(array);
}
}
}
}
}冒泡排序是稳定的排序算法，最容易实现的排序, 最坏的情况是每次都需要交换, 共需 遍历 并交换将近n²/2次, 时间 复杂度为O(n²). 最佳的情况是内循环遍历一次后发现排序是对的, 因此退出循环, 时间复杂度为O(n). 平均来讲, 时间复杂度为O(n²). 由于冒泡排序中只有 缓存 的temp变量需要内存 空间 , 因此空间复杂度为常量O(1)。
快速排序（Quicksort）是对冒泡排序的一种改进，借用了分治的思想，由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以 递归 进行，以此达到整个数据变成有序序列。
快速排序使用分治策略来把一个序列（ list ）分为两个子序列（sub-lists）。步骤为：
①. 从数列中挑出一个元素，称为”基准”（pivot）。
②. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。
在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
③. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，
它至少会把一个元素摆到它最后的位置去。
①. 挖坑法 用伪代码描述如下：
（1）low = L; high = R; 将基准数挖出形成第一个坑a[low]。
（2）high–，由后向前找比它小的数，找到后挖出此数填前一个坑a[low]中。
（3）low++，由前向后找比它大的数，找到后也挖出此数填到前一个坑a[high]中。
（4）再重复执行②，③二步，直到low==high，将基准数填入a[low]中。
举例说明： 一个无序数组：[4, 3, 7, 5, 10, 9, 1, 6, 8, 2]
（1）随便先挖个坑，就在第一个元素（基准元素）挖坑，挖出来的“萝卜”（第一个元素4）在“篮子”（临时变量）里备用。
挖完之后的数组是这样：[ 坑, 3, 7, 5, 10, 9, 1, 6, 8,2]
（2）挖右坑填左坑：从右边开始，找个比“萝卜”（元素4）小的元素，挖出来，填到前一个坑里面。 填坑之后：[ 2, 3,
7, 5, 10, 9, 1, 6, 8,坑]
（3）挖左坑填右坑：从左边开始，找个比“萝卜”（元素4）大的元素，挖出来，填到右边的坑里面。 填坑之后：[ 2, 3,
坑, 5, 10, 9, 1, 6, 8, 7]
（4）挖右坑填左坑：从右边开始，找个比“萝卜”（元素4）小的元素，挖出来，填到前一个坑里面。 填坑之后：[ 2, 3,
1, 5, 10, 9,坑, 6, 8, 7]
（5）挖左坑填右坑：从左边开始，找个比“萝卜”（元素4）大的元素，挖出来，填到右边的坑里面。 填坑之后：[ 2, 3,
1,坑, 10, 9, 5, 6, 8, 7]
（6）挖右坑填左坑：从右边开始，找个比“萝卜”（元素4）小的元素，挖出来，填到前一个坑里面，这一次找坑的过程中，
找到了上一次挖的坑了，说明可以停了，用篮子里的的萝卜，把这个坑填了就行了，并且返回这个坑的位置，作为分而治之
的中轴线。 填坑之后：[ 2, 3, 1, 4, 10, 9, 5, 6, 8, 7]
package com.bobo.dataStructure.sort;
import com.bobo.dataStructure.util.ArrayUtil;
/**
* 快速排序
*/
public class QuickSort implements BaseSort {
public static void main(String[] args) {
int[] array = {5, 4, 3, 2, 1};
BaseSort baseSort = new QuickSort();
baseSort.sort(array);
ArrayUtil.printArray(array);
}
@Override
public void sort(int[] array) {
quickSort(array,0,array.length-1);
}
/**
* 快速排序（挖坑法递归）
* @param arr 待排序数组
* @param low 左边界
* @param high 右边界
*/
public void quickSort(int arr[], int low, int high) {
if (arr == null || arr.length <= 0) {
return;
}
if (low >= high) {
return;
}
int left = low;
int right = high;
//挖坑1：保存基准的值
int temp = arr[left];
while (left < right) {
while (left < right && arr[right] >= temp) {
right--;
}
//坑2：从后向前找到比基准小的元素，插入到基准位置坑1中
arr[left] = arr[right];
while (left < right && arr[left] <= temp) {
left ++;
}
//坑3：从前往后找到比基准大的元素，放到刚才挖的坑2中
arr[right] = arr[left];
}
//基准值填补到坑3中，准备分治递归快排
arr[left] = temp;
quickSort(arr, low, left-1);
quickSort(arr, left + 1, high);
}
}快速排序的时间复杂度是O(nlogn),空间复杂度是O(1)。
直接插入排序的基本思想是：将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过为止。
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
①. 从第一个元素开始，该元素可以认为已经被排序
②. 取出下一个元素，在已经排序的元素序列中从后向前扫描
③. 如果该元素（已排序）大于新元素，将该元素移到下一位置
④. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
⑤. 将新元素插入到该位置后
⑥. 重复步骤②~⑤
package com.bobo.dataStructure.sort;
import com.bobo.dataStructure.util.ArrayUtil;
/**
* @author wuxiaobo
* 直接插入排序
*/
public class InsertSort implements BaseSort {
public static void main(String[] args) {
int[] array = {5, 4, 3, 2, 1};
BaseSort baseSort = new InsertSort();
baseSort.sort(array);
ArrayUtil.printArray(array);
}
@Override
public void sort(int[] array) {
if (array == null || array.length == 0) {
return;
}
for (int i =0; i< array.length; i++) {
for (int j= i+1; j < array.length; j++) {
if (array[j] < array[i]) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
}
}插入排序平均复杂度是O(n 2 ),空间复杂度是O(1)。