- 一、 插入排序
- 1、 直接插入排序
- 2、希尔排序（缩小增量排序）
- 二、选择排序
- 1、直接选择排序：
- 2、堆排序：
- 三、交换排序
- 1、冒泡排序：
- 2、快速排序：
- 四、归并排序
- 五、非比较排序
- 1、计数排序：
1、 直接插入排序插入排序基本思想：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。
直接插入排序：当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。
动图演示：
代码部分：
import java.util.Arrays;
//直接插入排序
public class InsertSort {
public static void insertSort(int[] array){
//外层循环：每进行一次，拿到待排序的元素key以及已经排好序列的最后一个下标。
for(int i=0;i=0&&key
特性：
时间复杂度：O（N^2); （最优情况下O（N））
空间复杂度：O(1);
应用场景：序列接近有序时或者数据的量比较小的情况下，直接插入排序的时间效率越高。
稳定性：稳定。
2、希尔排序（缩小增量排序）
希尔排序：希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数gap，把待排序文件中所有记录分成个组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后，取一个较小的gap，重复上述分组和排序的工作。当该整数等于1时，所有记录在统一组内排好序。
动图演示：
代码部分：
import java.util.Arrays;
//希尔排序
public class ShellSort {
public static void shellSort(int[] array) {
int gap = array.length;
while (gap>1) {
//获取第一个gap
gap=(gap/3)+1;
for (int i = gap; i < array.length; i++) {
int key = array[i];
int end = i - gap;
while (end >= 0 && key < array[end]) {
array[end + gap] = array[end];
end -= gap;
}
array[end + gap] = key;
}
}
}
public static void main(String[] args) {
int[] array={9,8,7,6,5,4,3,2,1};
shellSort(array);
System.out.println(Arrays.toString(array));
}
}
特性:
时间复杂度：
空间复杂度：O（1)
应用场景： 数据量比较大，且比较随机
稳定性：不稳定。
二、选择排序
选择排序基本思想:每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
1、直接选择排序：
直接插入排序：在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素。若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换。在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素。
动图演示：（此过程为找最小值）
代码部分：
import java.util.Arrays;
//选择排序
public class SelectSort {
public static void swap(int[] array,int left,int right){
int temp=array[left];
array[left]=array[right];
array[right]=temp;
}
public static void selectSort(int[] array){
int size=array.length;
for(int i=0;iarray[pos]){
pos=j;
}
}
//如果当前获取最大值的下标不在当前序列的最后，则交换两位置的元素。
if(pos!=size-1-i){
swap(array,pos,size-1-i);
}
}
}
public static void main(String[] args) {
int[] array={9,8,7,6,5,4,3,2,1};
selectSort(array);
System.out.println(Arrays.toString(array));
}
}
特性：
时间复杂度：O（N^2)
空间复杂度：O(1)
应用场景： 数据量不大时
稳定性：不稳定
2、堆排序：
堆排序：堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
动图演示：
代码部分：
import java.util.Arrays;
//堆排序
public class HeapSort {
public static void swap(int[] array, int left, int right) {
int temp = array[left];
array[left] = array[right];
array[right] = temp;
}
//向下调整堆
public static void shiftDown(int[] array, int size, int parent) {
int child=2*parent+1;
while(childarray[child]){
child+=1;
}
if(array[parent]= 0; root--) {
shiftDown(array, array.length, root);
}
//end标记最后一个结点
int end = array.length - 1;
while (end >0) {
//交换当前堆顶元素和end位置元素的位置。
swap(array, 0, end);
//然后再次调整堆，此时shiftDown方法中的参数end，使得最后一个元素的位置已经固定。
shiftDown(array, end, 0);
//end前移。
end--;
}
}
public static void main(String[] args) {
int[] array={1,8,3,5,9,2,4,6,7};
heapSort(array);
System.out.println(Arrays.toString(array));
}
}
特性：
时间复杂度： O(N*logN）
空间复杂度： O（1)
应用场景： top-k
稳定性：不稳定
三、交换排序
交换排序基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
1、冒泡排序：
冒泡排序基本思想：根据大小关系，不断交换相邻两记录的位置，每遍历结束一次后，序列最后一个位置就是最大的记录，此时不用再关心最后一个元素，对前N-1个记录进行上述同样的操作。
动图演示：
代码部分：
import java.util.Arrays;
//冒泡排序
public class BubbleSort {
public static void bubbleSort(int [] array){
//外层循环：需要遍历的趟数
for(int i=0;i而不是>=,否则会导致排序不稳定。
if(array[j]>(array[j+1])){
flag=1;
int temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
//检测此趟排序是否发生了元素的交换，若没有，则直接return.
if(flag==0){
return;
}
}
}
public static void main(String[] args) {
int[] array={1,3,2,7,5,4,6,9,8};
bubbleSort(array);
System.out.println(Arrays.toString(array));
}
}
特性：
时间复杂度：O（N^2)
空间复杂度： O（1）
应用场景： 一般不适用，效率太低
稳定性：稳定
2、快速排序：
快速排序基本思想：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
动图演示：
代码部分（优化版）：
一般情况下，我们会取序列的最后一个元素作为基准值，但是当最后一个元素的位置过于偏的时候，会使得效率降低，所以下面代码使用三数取中法，取得一个比较靠中间的基准值，一定程度上提高了程序的效率。
import java.util.Arrays;
//快速排序
public class QuickSort {
//三数取中法：希望在取基准值时尽可能取到一个数值靠中间的数，提高算法效率
public static int getIndexOfMiddle(int[] array, int left, int right) {
//拿到中间位置的下标
int mid = left + ((right - left) >> 1);
//判断left、right-1位置处的元素大小
//当left处的值小于right-1处的值时，
if (array[left] < array[right - 1]) {
//此时如果mid处的值还小于left处的值，那么中间数就为left处的值
if (array[mid] < array[left]) {
return left;
} else if (array[mid] > array[right - 1]) {//如果mid处的值还大于right-1处的值，那么中间数就为right-1处的值
return right - 1;
} else {//否则，中间数为mid处的值
return mid;
}
} else {
if (array[mid] > array[left]) {
return left;
} else if (array[mid] < array[right - 1]) {
return right - 1;
} else {
return mid;
}
}
}
public static int partation(int[] array,int left,int right) {
//通过三数取中法得到基准值下标
int index = getIndexOfMiddle(array, left, right);
//将基准值与最后一个元素位置互换
if (index != right - 1) {
int ret = array[index];
array[index] = array[right - 1];
array[right - 1] = ret;
}
//用key来标记基准值
int key = array[right - 1];
//left和end分别指向数组的第一个元素和最后一个元素
int begin = left;
int end = right - 1;
//循环条件：begin= key) {
end--;
}
//如果begin不等于end,那么基准值的位置还没有找到
if (begin != end) {
//交换上述找到的两个元素
int ret = array[begin];
array[begin] = array[end];
array[end] = ret;
}
}
//结束循环之后，begin和end指向同一个元素，那么基准值的位置就找到了，交换该位置元素与最后一个基准值元素
if (begin != right - 1) {
int ret = array[begin];
array[begin] = array[right - 1];
array[right - 1] = ret;
}
//返回基准值位置
return begin;
}
//
public static void quickSort(int[] array,int left,int right) {
if (right - left > 1) {
//找到基准值的位置
int div = partation(array, left, right);
//以基准值为界，对左侧[left,div)、右侧[div+1,right)分别进行quickSort（递归）
quickSort(array, left, div);
quickSort(array, div + 1, right);
}
}
//包装一下quickSort,避免参数过多
public static void quickSort(int[] array){
// [0, array.length)
quickSort(array,0,array.length);
}
public static void main(String[] args) {
int[] a={5,8,2,3,7,9,1,4,10,6};
quickSort(a);
System.out.println(Arrays.toString(a));
}
}
特性：
时间复杂度：O(N*logN)
空间复杂度：O (logN)
应用场景：数据越随机越好
稳定性：不稳定
四、归并排序
归并排序基本思想：归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
动图演示：
代码部分：
import java.util.Arrays;
//归并排序
public class MergeSort {
public static void mergeData(int[] array,int left,int mid,int right,int[] temp){
int begine1=left;
int end1=mid;
int begine2=mid;
int end2=right;
int index=left;
while(begine1 1){
//取中间位置
int mid=left+((right-left)>>1);
//递归排序左侧和右侧，注意区间为 [left,mid) 和 [mid,right)左闭右开
mergeSort(array,left,mid,temp);
mergeSort(array,mid,right,temp);
//此时开始“归并”中的“并”
mergeData(array,left,mid,right,temp);
//调用arraycopy方法，将已经排好的temp数组中的内容拷贝到array中去。
System.arraycopy(temp,left,array,left,right-left);
}
}
//将归并排序包装一下，避免参数过多
public static void mergeSort(int[] array){
//定义一个待排序数组array长度的数组
int[] temp=new int[array.length];
//归并排序
mergeSort(array,0,array.length,temp);
}
public static void main(String[] args) {
int[] array={1,3,6,4,2,8,10,0,5};
mergeSort(array);
System.out.println(Arrays.toString(array));
}
}
特性：
时间复杂度： O（N*logN）
空间复杂度： O（N）
应用场景： 外部排序
稳定性：稳定
五、非比较排序
1、计数排序：
基数排序基本思想：统计相同元素出现次数，然后根据统计的结果将序列回收到原来的序列中。
动图演示：
代码部分：
import java.util.Arrays;
//计数排序
public class CountSort {
public static void countSort(int[] array){
//记录数组中的最大值和最小值
int maxvalue=array[0];
int minvalue=array[0];
for(int i=0;imaxvalue){
maxvalue=array[i];
}
if(array[i]
此种情况仅适用于序列号是从0开始的，如果给出的序列号集中在某一个区间之内，那么count数组的下标就不能表示为元素本身，需要做一些修改，假设此时我们给出的序列集中在[20-30]之间，那么修改后的代码如下：
import java.util.Arrays;
//计数排序
public class CountSort {
public static void countSort(int[] array){
//记录数组中的最大值和最小值
int maxvalue=array[0];
int minvalue=array[0];
for(int i=0;imaxvalue){
maxvalue=array[i];
}
if(array[i]
特性：
时间复杂度： O（N）N为元素的个数
空间复杂度：O（M）M为数据的范围
应用场景： 数据密集的集中在某个范围当中
稳定性：稳定
作者:luka.lh
喜欢请关注哦！
