数据结构~七大排序算法(Java实现)

目录

插入排序

直接插入排序

希尔排序

选择排序

直接选择排序

堆排序

交换排序

冒泡排序

快速排序

递归实现

优化版本

归并排序 

---

插入排序

直接插入排序

public class MySort {public static void insertSort(int[] array) {for (int i = 1; i < array.length; i++) {int j = i - 1;int tmp = array[i];for (; j >= 0; j--) {if (tmp < array[j]) {array[j + 1] = array[j];} else {break;}}array[j + 1] = tmp;}}
}

· 时间复杂度：

        最好情况下O(n)，即数组有序的情况

        最坏情况下O(n^2)，即数组逆序的情况

· 空间复杂度：O(1)

· 稳定性： 稳定的排序算法

希尔排序

public class MySort {public static void shellSort(int[] array) {for (int gap = array.length / 2; gap > 1; gap /= 2) {shell(array, gap);}shell(array, 1);}private static void shell(int[] array, int gap) {for (int i = gap; i < array.length; i++) {int j = i - gap;int tmp = array[i];for (; j >= 0; j -= gap) {if (tmp < array[j]) {array[j + gap] = array[j];} else {break;}}array[j + gap] = tmp;}}
}

· 时间复杂度：O(n^1.3)

· 空间复杂度：O(1)

· 稳定性： 不稳定的排序算法

选择排序

直接选择排序

public class MySort {public static void selectSort(int[] array) {for (int i = 0; i < array.length; i++) {int minIndex = i;for (int j = i + 1; j < array.length; j++) {if (array[minIndex] > array[j]) {minIndex = j;}}swap(array, minIndex, i);}}private static void swap(int[] array, int i, int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}
}

· 时间复杂度：O(n^2)

· 空间复杂度：O(1)

· 稳定性：不稳定的排序算法 

堆排序

要排升序时，建立大根堆，排降序时，建立小根堆

public class MySort {public static void heapSort(int[] array) {//1、建立大根堆  时间复杂度：O(n)createHeap(array);//2、排序  时间复杂度：O(n*logn)int end = array.length - 1;while (end > 0) {swap(array, 0, end);shiftDown(array, 0, end);end--;}}private static void createHeap(int[] array) {for (int parent = (array.length-1-1) / 2; parent >= 0; parent--) {shiftDown(array, parent, array.length);}}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;}}}private static void swap(int[] array, int i, int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}
}

· 时间复杂度：O(n*logn)  和数据是否有序无关

· 空间复杂度：O(1)

· 稳定性：不稳定的排序算法 

交换排序

冒泡排序

public class MySort {public static void bubbleSort(int[] array) {for (int i = 0; i < array.length; i++) {boolean flag = false;for (int j = 0; j < array.length - i - 1; j++) {if (array[j + 1] < array[j]) {swap(array, j + 1, j);flag = true;}}if (flag == false) {return;}}}private static void swap(int[] array, int i, int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}
}

· 时间复杂度：O(n^2)，优化后的冒泡排序时间复杂度最好可以到O(n)

· 空间复杂度：O(1)

· 稳定性：稳定的排序算法 

快速排序

· 时间复杂度：

        最好情况下：O(n*logn)，待排序列尽量均匀的分割

        最坏情况下：O(n^2)，待排序列正序或逆序

· 空间复杂度：

        最好情况下：O(logn)

        最坏情况下：O(n)

· 稳定性：不稳定的排序算法 

递归实现

public class MySort {public static void quickSort(int[] array) {quick(array, 0, array.length - 1);}private static void quick(int[] array, int start, int end) {if (start >= end) {return;}int pivot = partition(array, start, end);quick(array, start, pivot - 1);quick(array, pivot + 1, end);}private static int partition(int[] array, int left, int right) {int tmp = array[left];while (left < right) {while (left < right && array[right] >= tmp) {right--;}array[left] = array[right];while (left < right && array[left] <= tmp) {left++;}array[right] = array[left];}array[left] = tmp;return left;}
}

优化版本

对于快速排序的优化，利用三数取中法选取key值，当递归到小的区间时，采用直接插入排序

public class MyQuickSort {private static final int INSERT_SIZE = 100;private static void quickSort(int[] array) {quick(array, 0, array.length - 1);}private static void quick(int[] array, int start, int end) {if (start >= end) {return;}if (end - start + 1 <= INSERT_SIZE) {insertSort(array, start, end);return;}int index = threeMid(array, start, end);swap(array, start, index);int pivot = partition(array, start, end);quick(array, start, pivot - 1);quick(array, pivot + 1, end);}/*** 针对快排的优化：key值根据三数取中法获得*/private static int threeMid(int[] array, int left, int right) {int mid = (left + right) >>> 1;if (array[left] > array[right]) {if (array[mid] > array[left]) {return left;} else if (array[mid] < array[right]) {return right;} else {return mid;}} else {if (array[mid] > array[right]) {return right;} else if (array[mid] < array[left]) {return left;} else {return mid;}}}/*** 针对快排的优化：当递归到小的区间时，快排转为插入排序*/private static void insertSort(int[] array, int start, int end) {for (int i = start + 1; i < end + 1; i++) {int j = i - 1;int tmp = array[i];for (; j >= start; j--) {if (tmp < array[j]) {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 (left < right && array[right] > tmp) {right--;}array[left] = array[right];while (left < right && array[left] < tmp) {left++;}array[right] = array[left];}array[left] = tmp;return left;}private static void swap(int[] array, int i, int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}
}

归并排序 

public class MySort {public static void mergeSort(int[] array) {mergeSortFunction(array, 0, array.length - 1);}private static void mergeSortFunction(int[] array, int low, int high) {if (low >= high) {return;}int mid = (low + high) >>> 1;mergeSortFunction(array, low, mid);mergeSortFunction(array, mid + 1, high);merge(array, low, high, mid);}private static void merge(int[] array, int low, int high, int mid) {int[] tmp = new int[high - low + 1];int k = 0;int start1 = low;int end1 = mid;int start2 = mid + 1;int end2 = high;while (start1 <= end1 && start2 <= end2) {if (array[start1] < array[start2]) {tmp[k++] = array[start1++];} else {tmp[k++] = array[start2++];}}while (start1 <= end1) {tmp[k++] = array[start1++];}while (start2 <= end2) {tmp[k++] = array[start2++];}for (int i = 0; i < k; i++) {array[i + low] = tmp[i];}}

· 时间复杂度：O(n*logn)，不论有序或无序都是O(n*logn)

· 空间复杂度：O(n)

· 稳定性： 稳定的排序算法