排序方法 平均时间 最好时间 最坏时间
桶排序(不稳定) O(n) O(n) O(n)
基数排序(稳定) O(n) O(n) O(n)
归并排序(稳定) O(nlogn) O(nlogn) O(nlogn)
快速排序(不稳定) O(nlogn) O(nlogn) O(n^2)
堆排序(不稳定) O(nlogn) O(nlogn) O(nlogn)
希尔排序(不稳定) O(n^1.25)
冒泡排序(稳定) O(n^2) O(n) O(n^2)
选择排序(不稳定) O(n^2) O(n^2) O(n^2)
直接插入排序(稳定) O(n^2) O(n) O(n^2)
快速排序空间复杂度为logn(因为递归调用了) ,归并排序空间复杂是O(n),需要一个大小为n的临时数组.
基数排序的空间复杂是O(n),
冒泡排序
冒泡排序的基本思想是，对相邻的元素进行两两比较，如果第一个比第二个大，就交换他们两个，以此类推，这样，每一趟会将最大的元素放到最后。
/**
* 时间复杂度：最好情形O(n)，平均情形O(n^2)，最差情形O(n^2)
* 空间复杂度：O(1)
* 稳 定 性：稳定
*/
class Solution {
public void bubbleSort(int[] nums) {
//轮数
for (int i=0; i<nums.length ;++i){
//每一轮的处理
for (int j=0; j<nums.length-1-i ;++j){
if (nums[j+1] < nums[j]){
int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
}
}
该排序有优化的地方，当数组已经有序，还会继续剩下的轮数，可以设一个标志变量，当某一轮没有进行交换处理，说明已经有序，直接跳出循环。
class Solution {
public void sortColors(int[] nums) {
for (int i=0; i<nums.length ;++i){
boolean flag = true;
for (int j=0; j<nums.length-1-i ;++j){
if (nums[j+1] < nums[j]){
int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
//有进行交换处理，说明不是有序，标记变为false
flag = false;
}
}
//如果已经有序，直接跳出
if(flag){
break;
}
}
}
}
有一种情况，如下所示
3，1，5，4，6，7，8，9
数组后四位数是有序的，则意味着每轮的交换的处理到这后四位，位置都不变，白白比较多次，是没有意义的，所以我们需要进行有序区间的划分，记住每一轮的最后一次交换的处理的位置
class Solution {
public void sortColors(int[] nums) {
int border = nums.length-1;
int lastIndex = 0;
for (int i=0; i<nums.length ;++i){
boolean flag = true;
for (int j=0; j<border ;++j){
if (nums[j+1] < nums[j]){
int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
flag = false;
lastIndex = j;
}
}
border = lastIndex;
if(flag){
break;
}
}
}
}
鸡尾酒排序是冒泡排序的一种变形。此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。
那么为什么要有鸡尾酒排序呢？
有一种情况：2，3，4，5，6，1
在这种情况下，冒泡排序得进行5轮排序，可2-6已经是有序，就为了一个1，而进行5轮排序，鸡尾酒排序就是为了解决这种情况
冒泡排序一直是单向处理，从左到右，而鸡尾酒排序是第一轮从左到右，第二轮从右到左，第三轮再从左到右，以此类推
class Solution {
public void sortColors(int[] nums) {
int left = 0, right = nums.length-1;
while (left < right){
for (int i=left; i<right; ++i){
if (nums[i] > nums[i+1]){
int temp = nums[i];
nums[i] = nums[i+1];
nums[i+1] = temp;
}
}
right--;
for (int j=right; j>left; j--){
if (nums[j-1] >nums[j]){
int temp = nums[j-1];
nums[j-1] =nums[j];
nums[j] = temp;
}
}
left++;
}
}
}
冒泡排序在数组有序的情况下，最好的时间复杂度为O(n)；
在数组逆序的情况下，最坏情况下的时间复杂度为O(n^2)；
空间复杂度为O(1)；
排序过程中，相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
快速排序
基本思想：每一轮排序选择一个基准元素，小于等于它的数放在左边，大于它的数放在右边，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行。
/**
* Title: 交换排序中的快速排序，目前应用最为广泛的排序算法，是一个递归算法，依赖于初始序列
* Description:快速排序包括两个过程：划分 和 快排
* "划分"是指将原序列按基准元素划分两个子序列
* "快排"是指分别对子序列进行快排
*
* 就平均计算时间而言，快速排序是所有内部排序方法中最好的一个
*
* 对大规模数据排序时，快排是快的；对小规模数据排序时，快排是慢的，甚至慢于简单选择排序等简单排序方法
*
* 快速排序依赖于原始序列，因此其时间复杂度从O(nlgn)到O(n^2)不等
* 时间复杂度：最好情形O(nlgn)，平均情形O(nlgn)，最差情形O(n^2)
*
* 递归所消耗的栈空间
* 空间复杂度：O(lgn)
*
* 可选任一元素作为基准元素
* 稳 定 性：不稳定
*/
public static void quickSort(int[] nums, int left, int right){
if (left >= right) {
return ;
}
int pos = partition(nums, left, right);
quickSort(nums, left, pos - 1);
quickSort(nums, pos + 1, right);
}
public static int partition(int[] nums, int left, int right){
int temp = nums[left];
while (left < right) {
while (left < right && nums[right] > temp) {
right--;
}
if (left < right) {
nums[left] = nums[right];
}
while (left < right && nums[left] <= temp) {
left++;
}
if (left < right) {
nums[right] = nums[left];
}
}
nums[left] = temp;
return left;
}
public static void quickSort(int[] nums) {
quickSort(nums, 0, nums.length - 1);
}
快速排序平均时间复杂度为O(N*logN)，但如果应用于逆序的数组，第一个数为最大值或最小值，时间复杂度变为O(N^2),为了避免这种情况，可以随机选择一个基准元素，当然了，也有一点几率选择到最大值或最小值，它是一种不稳定算法，意味着多个相同的值的相对位置也许会在算法结束时产生变动。
归并排序
基本思想：利用分治法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，将子序列再分为两组，一直到分到的小组只有一个数，再将相邻的小组合并，合并成一个完整的有序的序列。
/**
* 归并排序的主要问题是：需要一个与原待排序数组一样大的辅助数组空间
*
* 归并排序不依赖于原始序列，因此其最好情形、平均情形和最差情形时间复杂度都一样
* 空间复杂度：O(n) 稳 定 性：稳定 内部排序(在排序过程中数据元素完全在内存)
*/
public void mergeSort(int[] nums, int left, int right){
if (left < right){
int mid = left + (right - left)/2;
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
merge(nums, left, mid, mid + 1, right);
}
}
public void merge(int[] nums, int L1, int R1, int L2, int R2){
int[] temp = new int[R2 - L1 + 1];
int i = L1;
int j = L2;
int k = 0;
while (i <= R1 && j <= R2){
if (nums[i] > nums[j]){
temp[k] = nums[j];
k++;
j++;
}else{
temp[k] = nums[i];
k++;
i++;
}
}
while (i <= R1){
temp[k] = nums[i];
i++;
k++;
}
while (j <= R2){
temp[k] = nums[j];
j++;
k++;
}
for (int c=0; c<k; ++c){
nums[L1+c] = temp[c];
}
}
归并排序的时间复杂度为O(N*logN)，稳定的排序算法
堆排序
堆分为大根堆和小根堆，是完全二叉树。大根堆的要求任何一个父节点的值，都大于等于它左右孩子节点的值，小根堆任何一个父节点的值，都小于等于它左右孩子节点的值。决定了在大根堆的堆顶是整个堆中的最大元素；小根堆的堆顶是整个堆中的最小元素
举例：小根堆的插入是插入最后一个位置，之后根据与父节点大小，决定是否上浮；小根堆的删除堆顶结点，把最后一个数放到堆顶位置，然后下浮，调整树
二叉堆的所有节点都存储在数组当中，父节点的下标是parent，那么它的左孩子下标就是 2parent；它的右孩子下标就是 2parent+1
将数组创建为大根堆，每次将第一个数与最后一个数交换，数组个数减一，以此类推，形成升序数组
/**
* Title: 堆排序(选择排序)，升序排序(最大堆)，依赖于初始序列
* 时间复杂度：O(nlgn)
* 空间复杂度：O(1)
* 稳 定 性：不稳定
* 内部排序(在排序过程中数据元素完全在内存)
*/
public void downAdjust(int low, int high, int[] nums){
int parentIndex = low, childIndex = 2 * parentIndex;
while (childIndex <= high){
if (childIndex + 1 <= high && nums[childIndex + 1] > nums[childIndex]){
childIndex = childIndex + 1;
}
if (nums[childIndex] > nums[parentIndex]){
swap(nums, parentIndex, childIndex);
parentIndex = childIndex;
childIndex = 2 * parentIndex;
}else{
break;
}
}
}
public void createHeap(int[] nums){
for (int i = nums.length / 2; i >= 0; --i){
downAdjust(i, nums.length-1, nums);
}
}
public void heapSort(int[] nums){
createHeap(nums);
for (int i = nums.length - 1; i >= 0; i--){
swap(nums, i, 0);
downAdjust(0, i - 1, nums);
}
}
堆排序的时间复杂度为O(N * logN)，它是不稳定的排序方法
插入排序
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
/**
* Title: 插入排序中的直接插入排序，依赖于初始序列
* 时间复杂度：最好情形O(n)，
平均情形O(n^2)，
最差情形O(n^2)
* 空间复杂度：O(1)
* 稳定性：稳定
* 内部排序(在排序过程中数据元素完全在内存)
*/
public static void insertionSort(int[] arr) {
int len = arr.length;
for (int i = 1; i < len; i++) {
int temp = arr[i];
int j = i - 1;
for (; j >= 0; j--) {
if (arr[j] > temp) {
arr[j + 1] = arr[j];
} else {
break;
}
}
arr[j + 1] = temp;
}
}
//插入排序2
public static void insertSort(int[] arr) {
int len = arr.length;
for (int i = 1; i < len; i++) {
for (int j = i; j > 0; j--) {
if (arr[j - 1] > arr[j]) {
int temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
} else {
break;
}
}
}
}
选择排序
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
/**
* Title: 选择排序中的直接选择排序，依赖于初始序列
* 时间复杂度：最好情形O(n^2)，平均情形O(n^2)，最差情形O(n^2)
* 空间复杂度：O(1)
* 稳 定 性：不稳定
*/
public static void selectionSort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len - 1; i++) {
int min = i;
for (int j = i + 1; j < len; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
网友评论