引言
排序算法是数据结构中最基本的算法之一，在现实生活中应用也非常广泛。常见的排序算法：
注：
1)本文所有代码的测试用例为
public static void main(String[] args) {
int[] array = {2,9,7,4,1,8,0,5,4,6};
System.out.println(Arrays.toString(array));
//排序算法
System.out.println(Arrays.toString(array));
}
2)本文实现的均为升序
3）本文的交换函数
public static void swap(int[] array,int i,int j){
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
4）测试优化程度代码
public static void main(String[] args) {
long start = System.currentTimeMillis();
Random random = new Random(10_0000);
int[] array = new int[10_0000];
//数组为有序数组
for (int i = 0; i < array.length; i++) {
array[i] = i;
}
// 数组为无序数组
// for (int i = 0; i < array.length; i++) {
// array[i] = random.nextInt();
// }
//排序算法
long end = System.currentTimeMillis();
System.out.println(end - start);
}
插入排序
直接插入排序
插入排序是一种简单直观对的排序算法，打过扑克牌的同学应该都能秒懂，他的工作原理是先构建有序的序列，对未排序的数据，在已排序的序列中从后向前扫描，找到相应的位置并插入。
1） 算法步骤
首先将待排序的第一个序列的第一个元素看成有序序列，让后把第二个元素当成是未排序序列。从头到尾一次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（当待排序的元素的与有序序列中的某个元素相等，则将待排序的元素插入到相等元素的后面）
2） 动图演示
3） 代码实现
public static void insertSort(int[] array){
for (int i = 1; i < array.length; i++) {
int tmp = array[i];
int j = i - 1;
for ( ; j >= 0; j--) {
if (tmp < array[j]){
array[j + 1] = array[j];
}else {
break;
}
}
array[j + 1] = tmp;
}
}
4）总结
时间复杂度平均为O（n^2）,最坏为O（n ^2),最好（当序列为有序时）为O（n）
空间复杂度为O(1)，
稳定性：稳定。
希尔排序
希尔排序（Shell Sort），是插入排序的一种改进版，但是希尔排序是非稳定的排序。
希尔排序的基本思想是：先将整个待排序的循序分成若干个子序列分别进行直接插入排序，待整个序列的趋于有序时在进行直接插入排序。
1）算法步骤
选择一个增量gap,根据间隔gap进行分组，对每组进行直接插入排序，然后通过gap /= 2;来改变分组的距离，在分别对每组进行直接插入排序，知道gap=1,是就是对整个序列进行插入排序。（当序列趋于有序时直接插入排序越快）
2）动图演示
3）代码实现
public static void shell(int[] array,int gap){
for (int i = gap; i <array.length ; i++) {
int tmp = array[i];
int j = i - gap;
for (; j >= 0 ; j -= gap) {
if (tmp < array[j]){
array[j + gap] = array[j];
}else {
break;
}
}
array[j + gap] = tmp;
}
}
public static void shellSort(int[] array){
int gap = array.length;
while (gap > 1){
gap /= 2;
shell(array,gap);
}
}
4）总结
时间复杂度：O（n^1.3 - n ^1.5）
空间复杂度为：O（1）
稳定性：不稳定
选择排序
选择排序
选择排序是一种简单直观的排序算法，无论什么数据的时间复杂度都为O（n^2）。
1）算法步骤
第一步，首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。第二步，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。重复第二步，直到所有元素均排序完毕。
2）动图演示
3)代码实现
public static void selectSort(int[] array){
for (int i = 0; i < array.length; i++) {
int min = i;
for (int j = i ; j < array.length; j++) {
if (array[j] < array[min]){
min = j;
}
}
swap(array,i,min);
}
}
4）总结
时间复杂度：O（n^2）
空间复杂度：O（1）
稳定性：不稳定
堆排序
堆排序，是利用堆这种数据结构所设计的一种排序算法。堆是一个近似的完全二叉树的结构。并且都满足堆积的性质：即子节点的值总是小于或大于父节点的值。
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序中用于升序排列。
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序中用于降序排列。
1）算法步骤
1.先创建一个大堆。
2.交换堆顶与堆尾的值；
3.删除堆尾，并使用向下调整算法，将堆调整为大堆。
4.重复步骤2，知道只剩下堆顶元素。
2）动图演示
3）代码实现
public static void heapSort(int[] array){
//将大堆
creatBigHeap(array);
//交换堆顶与堆尾的位置
for (int i = array.length - 1; i > 0 ; i--) {
swap(array,0, i);
//交换之后，再次调整为大堆
shiftDown(array,0,i);
}
}
//由于是升序建大堆
private static void creatBigHeap(int[] array) {
for (int parent = (array.length - 1) / 2; parent >= 0 ; parent--) {
shiftDown(array,parent, array.length - 1);
}
}
//向下调整算法
private static void shiftDown(int[] array, int parent,int len) {
int child = 2 * parent + 1;//默认为左孩子
while (child < len){
if (child + 1 < len && array[child] < array[child + 1]){
child++;
}
if (array[child] > array[parent]){
swap(array,child,parent);
parent = child;
child = 2 * parent + 1;
}else {
break;
}
}
}
4）总结
时间复杂度：为O（nlogn）
空间复杂度：O（1）
稳定性：不稳定
交换排序
冒泡排序
冒泡排序也是一种简单直观的排序算法。它重复地走访过要排序的序列，一次比较相邻的两个元素，如果前一个元素大于后一个元素的值，就交换这两个元素的值。从第一对比较到最后一对知道所以元素有序。
1）算法步骤
比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作相同的工作，从开始第一对到结尾的最后一对。这步完成之后，最后的元素就是序列中的最大值。针对所有的元素重复以上的步骤，除了最后一个。直到序列有序。
2）动图演示
3）代码实现
public static void bubbleSort(int[] array){
for (int i = 0; i < array.length; i++) {
for (int j = 1; j < array.length - i ; j++) {
if (array[j - 1] > array[j]){
swap(array,j - 1, j);
}
}
}
}
4）算法优化
设置一个flag = false，若在一趟排序之后元素没有发生交换，说明该序列已经有序，不需要在进行排序。
public static void bubbleSort(int[] array){
for (int i = 0; i < array.length; i++) {
boolean flag = false;
for (int j = 1; j < array.length - i ; j++) {
if (array[j - 1] > array[j]){
swap(array,j - 1, j);
flag = true;
}
}
if(flag == false){
break;
}
}
}
5)总结
时间复杂度：O（n^2）
空间复杂度：O（1）
稳定性：稳定
快速排序
快速排序是一种分而治之的思想，效率高，是处理大数据最快的排序算法之一了。
1）算法步骤
1.从序列中挑选一个元素作为基准（pivot）；
2.重新排序序列，所有元素比基准值小的放在基准的前面，所有元素比基准值大的摆在基准的后面。
3.递归地吧小于基准元素的子序列和大于基准值元素的子序列进行排序。
2）动图演示
3）代码实现
挖坑法：
public static void quickSort(int[] array,int left,int right){
if (left >= right){
return;
}
int piovt = partition(array,left,right);
quickSort(array,left,piovt - 1);
quickSort(array,piovt + 1, right);
}
private static int partition(int[] array, int left, int right) {
int tmp = array[left];
while (left < right){
while (array[right] >= tmp && left < right){
right--;
}
array[left] = array[right];
while (array[left] <= tmp && left < right){
left++;
}
array[right] = array[left];
}
array[left] = tmp;
return left;
}
hoare法
private static int partition1(int[] array, int left, int right) {
int tmp = array[left];
int start = left;
while (left < right){
while (array[right] >= tmp && left < right){
right--;
}
while (array[left] <= tmp && left < right){
left++;
}
swap(array,left,right);
}
swap(array,start,right);
return right;
}
4)算法优化
1）当每次选的基准是最大值或者最小值时，快排的效率就会降低，因此为了避免这种情况的出现，采用三数取中的方法来优化：选取left与right与他们的中值mid坐标中中间的那个值作为基准就可以避免基准是最大值或者最小值的情况。
代码实现：
public static void medianOfThree(int[] array,int left,int right){
int mid = (left + right) / 2;
if (array[mid] >array[left]){
swap(array,mid,left);
}// array[mid] <= array[left];
if (array[right] < array[left]){
swap(array,left,right);
}// array[left] <= array[right];
if (array[left] < array[mid]){
swap(array,mid,left);
}//保证了左边的数值为三个数的中间值
}
2）当序列趋于有序时快排花费的时间会比较长，所以当递归到一定区域时采用插入排序来进行优化。
public static void quickSort(int[] array,int left,int right){
if (left >= right){
return;
}
if (right - left < 100){
insertSort1(array,left,right);
}
// medianOfThree(array,left,right);
int piovt = partition(array,left,right);
quickSort(array,left,piovt - 1);
quickSort(array,piovt + 1, right);
}
private static void insertSort1(int[] array,int left,int right) {
for (int i = left + 1; i <= right; i++) {
int tmp = array[i];
int j = i - 1;
for (; j >= left ; j--) {
if (array[j] > tmp){
array[j + 1] = array[j];
}else {
break;
}
}
array[j + 1] = tmp;
}
}
private static int partition(int[] array, int left, int right) {
int tmp = array[left];
while (left < right){
while (array[right] >= tmp && left < right){
right--;
}
array[left] = array[right];
while (array[left] <= tmp && left < right){
left++;
}
array[right] = array[left];
}
array[left] = tmp;
return left;
}
5）非递归实现快速排序
public static void quickSortNor(int[] array){
Stack<Integer> stack = new Stack<>();
stack.push(array.length - 1);
stack.push(0);
while (!stack.isEmpty()){
int left = stack.pop();
int right = stack.pop();
if (left >= right){
continue;
}
int pivot = partition(array,left,right);
stack.push(pivot - 1);
stack.push(left);
stack.push(right);
stack.push(pivot + 1);
}
}
6）总结
时间复杂度为：O（nlogn）
空间复杂度为：O（logn）
稳定性：不稳定
归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的典型应用。
1)算法步骤
将序列的n个元素分成长度为1的子序列，让在两两合并为有序的序列，知道所有的序列有序。
2）动图演示
3）代码实现
public static void mergeSort2(int[] array){
mergeSortInternal2(array,0,array.length -1);
}
private static void mergeSortInternal2(int[] array, int left, int right) {
if (left>=right){
return;
}
int mid = (left + right) / 2;
//分为长度为1的区间
mergeSortInternal2(array,left,mid);
mergeSortInternal2(array,mid + 1, right);
int[] tmp = new int[right - left + 1];
int k = 0;
int s1 = left;
int e1 = mid;
int s2 = mid + 1;
int e2 = right;
// 合并
while (s1 <= e1 && s2 <= e2){
if (array[s1] < array[s2]){
tmp[k++] = array[s1++];
}else {
tmp[k++] = array[s2++];
}
}
while (s1 <= e1){
tmp[k++] = array[s1++];
}
while (s2 <= e2){
tmp[k++] = array[s2++];
}
for (int i = 0; i < k; i++) {
array[left + i] = tmp[i];
}
}
4）非递归实现
public static void mergeSortNor(int[] array){
int gap = 1;
for (int i = gap; i < array.length; i *= 2) {
merge2(array,i);
}
}
private static void merge2(int[] array, int gap) {
int s1 = 0;
int e1 = s1 + gap - 1;
int s2 = e1 + 1;
int e2 = (s2 + gap - 1 >= array.length - 1)? (array.length - 1) : (s2 + gap - 1);
int[] tmp = new int[array.length];
int k = 0;
//当有两个子序列时
while (s2 < array.length){
while (s1 <= e1 && s2 <= e2){
if (array[s1] < array[s2]){
tmp[k++] = array[s1++];
}else {
tmp[k++] = array[s2++];
}
}
while (s1 <= e1){
tmp[k++] = array[s1++];
}
while (s2 <= e2){
tmp[k++] = array[s2++];
}
s1 = e2 + 1;
e1 = s1 + gap - 1;
s2 = e1 + 1;
e2 = (s2 + gap - 1 >= array.length - 1)? (array.length - 1) : (s2 + gap - 1);
}
//当只有一个序列时
while (s1 <= array.length - 1){
tmp[k++] = array[s1++];
}
for (int i = 0; i < k; i++) {
array[i] = tmp[i];
}
}
5）总结
时间复杂度：O(nlogn)
空间复杂度：O（n）
稳定性：稳定
总结
