前言
算法对于我们普通的工程师来说可算得上陌生又熟悉，因为在平时的业务代码中可能见到他的身影比较少，但在底层的代码中我们可能会经常发现排序算法的影子，如数据库索引，操作系统的进程调度。因此，掌握这种算法中的思想还是致关重要，今天大猿就带大家来实战一下基础的排序算法，加强记忆。
常见的排序分类
直接插入排序
先直接上代码:
public static void insertSort2(int [] arr){
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j=i-1;
for ( ; j >= 0 ; j--) {
if(key < arr[j]){
arr[j + 1] = arr[j];
}else {
break;
}
}
arr[j + 1] = key;
}
StringBuffer stringBuffer = new StringBuffer();
for (int j : arr) {
stringBuffer.append(",").append(j);
}
System.out.println(stringBuffer);
}
public static void main(String[] args) {
int [] arr = {345,23,79,54,67,666,23,78,2,22,985};
// insertSort(arr);
insertSort2(arr);
}
运行结果
复杂度
时间复杂度
运行复杂度，当整个序列基本有序的情况下此时插入排序将出现最好情况 O(n) , 这个也不难想象，当整个排序序列基本有效时，比较只需要n次，内部循环几乎可以不执行。
对于一般情况时间复杂度是O(n^2);
空间复杂度
因为在程序执行过程中，我们只用一个一个临时存储变量，所以空间复杂度为O(1);
稳定性
该算法是稳定算法，如何理解稳定性呢？稳定性最直白的理解就是如果出现相同元素的时候，看原来的序列是否遭到破坏。
希尔排序
上代码，
public static void main(String[] args) {
int[] arr = new int[100];
for (int i = 0; i < 100; i++) {
arr[i] = (int) (Math.random() *100);
}
shellSort(arr);
}
public static void shellSort(int [] arr){
for (int gap = arr.length /2; gap>0; gap /=2){
for(int i = gap; i < arr.length ; i ++){
int temp = arr[i];
int j=i - gap;
for( ; j >= 0; j -= gap){
if(arr[j] < temp){
arr[j+gap]=arr[j];
}else {
break;
}
}
arr[j+gap] = temp;
}
}
StringBuffer stringBuffer = new StringBuffer();
for (int j : arr) {
stringBuffer.append(",").append(j);
}
System.out.println(stringBuffer);
}
运行结果
复杂度
时间复杂度
希尔排序可以理解为特殊的插入排序，最好和最坏时间复杂度基本与插入排序保持一致。软设上给出的平均复杂度为O(n^1.3) 有兴趣的同学可以去研究一下理论。
空间复杂度
空间复杂度基本与插入排序是一致的。
稳定性
该算法为非稳定算法。
计数排序
代码
public static int[] countSort(int[] array) {
//1.得到数列的最大值
int max = array[0];
for(int i=1; i<array.length; i++){
if(array[i] > max){
max = array[i];
}
}
//2.根据数列最大值确定统计数组的长度
int[] countArray = new int[max+1];
//3.遍历数列，填充统计数组
for(int i=0; i<array.length; i++){
countArray[array[i]]++;
}
//4.遍历统计数组，输出结果
int index = 0;
int[] sortedArray = new int[array.length];
for(int i=0; i<countArray.length; i++){
for(int j=0; j<countArray[i]; j++){
sortedArray[index++] = i;
}
}
return sortedArray;
}
public static int[] countSortV2(int[] array) {
//1.得到数列的最大值和最小值，并算出差值d
int max = array[0];
int min = array[0];
for(int i=1; i<array.length; i++) {
if(array[i] > max) {
max = array[i];
}
if(array[i] < min) {
min = array[i];
}
}
int d = max - min;
//2.创建统计数组并统计对应元素个数
int[] countArray = new int[d+1];
for(int i=0; i<array.length; i++) {
countArray[array[i]-min]++;
}
//3.统计数组做变形，后面的元素等于前面的元素之和
for(int i=1;i<countArray.length;i++) {
countArray[i] += countArray[i-1];
}
//4.倒序遍历原始数列，从统计数组找到正确位置，输出到结果数组
int[] sortedArray = new int[array.length];
for(int i=array.length-1;i>=0;i--) {
sortedArray[countArray[array[i]-min]-1]=array[i];
countArray[array[i]-min]--;
}
return sortedArray;
}
public static void main(String[] args) {
int[] array = new int[] {4,4,6,5,3,2,8,1,7,5,6,0,10};
int[] sortedArray = countSort(array);
System.out.println(Arrays.toString(sortedArray));
array = new int[] {95,94,91,98,99,90,99,93,91,92};
sortedArray = countSortV2(array);
System.out.println(Arrays.toString(sortedArray));
}
运行结果
时间复杂度
计数排序的时间复杂度为O(n+k)，其中n是待排序序列的长度，k是待排序序列中的最大值，注意计算时间复杂度时只是考虑了构造统计数组的最大长度k和
空间复杂度
计数排序的空间复杂度为O(k)。
稳定性
该算法是一个稳定算法，对于数的范围不大，但是算量很多的情况非常实用。
选择排序
继续先上代码
public static void selectSort(int [] arr){
int maxIndex =0;
for (int i = 0; i < arr.length-1; i++) {
for (int j = i; j <arr.length ; j++) {
if(arr[maxIndex]<arr[j]){
maxIndex =j;
}
}
if(maxIndex != i){
int temp =0;
temp = arr[maxIndex];
arr[maxIndex] = arr[i];
arr[i] = temp;
}
}
StringBuffer stringBuffer = new StringBuffer();
for (int i = 0; i <arr.length; i++) {
stringBuffer.append(",").append(arr[i]);
}
System.out.println(stringBuffer.toString());
}
public static void main(String[] args) {
int [] arr = {345,23,79,54,67,666,23,78,2,22,985};
selectSort(arr);
}
运行结果
时间和空间复杂度
选择排序的时间复杂度为O(n^2) 空间复杂度为O(1)
稳定性
该算法为不稳定算法。
堆排序
堆排序稍微复杂点，先上个截图，至于具体理论的话请同学们自己去找教材或者视频，下面给出算法及代码
public static void main(String[] args) {
int arr [] ={1,10,3,2,6,5,7,9,8,0,4};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
/**
*
* @param array
*/
private static void heapSort(int [] array){
//构建堆
for (int i = (array.length-2)/2; i >=0; i--) {
downAdjust(array,i,array.length);
}
System.out.println("-----------------------");
System.out.println(Arrays.toString(array));
//调整堆
for (int i = array.length-1; i >0; i--) {
int temp = array[i];
array[i] = array[0];
array[0] = temp;
downAdjust(array,0,i);
/* if("UP".equals(cmd)){
upAdjust(array);
}*/
}
}
/***
* 节点下沉
* @param arr
* @param parentIndex
* @param length
*/
private static void downAdjust(int [] arr,int parentIndex , int length){
int temp = arr[parentIndex];
int childIndex = 2* parentIndex +1;
while (childIndex < length){
//定位到右孩子
if(childIndex+1 < length && arr[childIndex+1]>arr[childIndex]){
childIndex++;
}
if(temp > arr[childIndex]){
break;
}
arr[parentIndex] = arr[childIndex];
parentIndex = childIndex;
childIndex = 2* childIndex+1;
}
arr[parentIndex] = temp;
// System.out.println(Arrays.toString(arr));
}
运行结果
复杂度及稳定性
堆排序是不稳定排序，其时间复杂度时O(nlog(2)n),空间复杂度为n+1；此外
该算法是非稳定算法。
冒泡排序
代码如下：
public static void main(String[] args) {
int [] arr = {345,23,79,54,67,666,23,78,2,22,985};
bubbleSort(arr);
}
public static void bubbleSort(int [] arr){
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
int temp = 0;
if (arr[j] < arr[j+1]) {
temp = arr[j];
arr[j]=arr[j+1];
arr[j+1] = temp;
}
}
}
StringBuffer stringBuffer = new StringBuffer();
for (int i = 0; i <arr.length; i++) {
stringBuffer.append(",").append(arr[i]);
}
System.out.println(stringBuffer.toString());
}
运行结果
复杂度分析及稳定性分析
冒泡算法的复杂度为O(n^2) 空间复杂度为O(1)，该算法为稳定的排序算法。
快速排序
主算法
public static void main(String[] args) {
int [] arr = {345,23,79,54,67,666,23,78,2,22,985};
quickSort(arr,0,arr.length-1);
StringBuffer stringBuffer = new StringBuffer();
for (int i = 0; i <arr.length; i++) {
stringBuffer.append(",").append(arr[i]);
}
System.out.println(stringBuffer.toString());
}
public static void quickSort(int [] arr, int start,int end){
if(start > end){
return;
}
int midIndex = partition(arr, start, end);
quickSort(arr,start,midIndex-1);
quickSort(arr,midIndex+1,end);
}
private static int partition(int[] arr, int start, int end) {
int right = end;
int left = start;
int midValue = arr[left];
while (left != right){
while (left<right && midValue < arr[right]){
right --;
}
// arr[left] = arr[right];
while (left<right && midValue >= arr[left]){
left ++;
}
// arr[right] = arr[left];
if(left < right){
int temp =0;
temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
arr[start] = arr[right];
arr[right] = midValue;
return right;
}
运行结果
复杂度分析
时间复杂度
快速排序的一般时间复杂度为 O(nlog(2)n) ,最坏的时间复杂度为O(n^2);
空间复杂度
递归算法的空间复杂度 = 每次递归的空间复杂度O(1) * 递归深度， 因为堆栈的深度就是快速排序的空间复杂度位O(log(2)n)，最坏也就是O(n)
稳定性
快速排序为不稳定算法
归并排序
先上代码
public static void main(String[] args) {
int [] arr = {345,23,79,54,67,666,23,78,2,22,985};
mergeSort(arr, 0, arr.length - 1);
for (int i : arr) {
System.out.print(i + " ");
}
}
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
public static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
for (int p = 0; p < temp.length; p++) {
arr[left + p] = temp[p];
}
}
运行结果
时间复杂度
从上面的代码来看，其归并的深度为log(2)n 而每次合并的时间复杂度都为n，所以综合下来其时间复杂度为 n*log(2)n;
空间复杂度
因为归并需要额外的空间数组，其大小n
稳定性
该算法为稳定的排序算法，相同元素不改变原来的位置。
桶排序
桶排序的基本思想可以说是与计数排序有异曲同工之妙，由于篇幅原因，需要了解算法的具体实现的小伙伴可以自己去翻阅资料。
总结
- 本文带大家实战了常见的排序算法，并给出了运行结果，其中采用 动态规划 思想的算法有 选择排序 ; 选择排序、冒泡排序和堆排序 都属于 贪心法，而 归并排序 采用了分治思想；希尔排序可以说是既采用了动态规划思想，又采用了分之思想；快速排序既采用贪心算法，又吸收了分治思想 。
- 对于不同场景我们可以采用不同的排序算法，从时间复杂度来看，快排，归并，堆排序是响应速度最快的三种常见排序方法，但所占空间都比较高；从空间复杂度来看，冒泡，插入，简单选择排序是应用空间最小的排序方法，但响应时间有点慢；复杂为线性的排序算法只有基数排序和桶排序，但该算法并不适合所有的应用场景，所以在实际应用大各位小伙伴要懂得权衡利弊，妥善处置。