冒泡排序
选择排序
插入排序
归并排序
快速排序
排序就是将输入的数字按照从小到大的顺序进行排列。
冒泡排序
冒泡排序就是重复从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字的位置。
在冒泡排序中 第一轮要比较n-1次，第二轮比较n-2次...第n-1轮需要比较1次，所以时间复杂度为O(n^2)
Tips:这里指n的平方
public int[] sort(int[] nums) {
for (int i=0; i<nums.length; i++) {
for (int j=0; j<nums.length-1-i; j++) {
int a = nums[j];
int b = nums[j+1];
if (a > b) {
nums[j] = b;
nums[j+1] = a;
}
}
}
return nums;
}
如果给定一个有序的数组，那么冒泡也会从头到尾遍历，这样会浪费很多资源，所以可以增加一个判断，看是否已经排序完成。代码如下：
public int[] sort(int[] nums) {
for (int i=0; i<nums.length; i++) {
boolean isSort = true;
for (int j=0; j<nums.length-i-1; j++) {
int a = nums[j];
int b = nums[j+1];
if (a > b) {
nums[j] = b;
nums[j+1] = a;
isSort = false;
}
}
if (isSort) {
break;
}
}
return nums;
}
选择排序
选择排序是重复从等待排序的数据中寻找最小值，将其与未排序的序列最左边的数字进行交换。
双层循环，时间复杂度为O(n^2)
public int[] sort(int[] nums) {
for (int i=0; i<nums.length; i++) {
int index = i;
for (int j=i+1; j<nums.length; j++) {
index = nums[index] > nums[j] ? j : index;
}
int temp = nums[i];
nums[i] = nums[index];
nums[index] = temp;
}
return nums;
}
插入排序
插入排序是一种从序列左端开始依次对数据进行排序的算法。
在排序的过程中，左侧的数据陆续归位，而右侧留下的就是还未排序的数据。
从右边拿到的数字还是要跟已经排序好的数字逐一比较，所以时间复杂度还是O(n^2)
public int[] sort(int[] nums) {
for (int i=0; i<nums.length-1; i++) {
int tempIndex = i + 1;
while (tempIndex > 0) {
if (nums[tempIndex] > nums[tempIndex-1]) {
break;
}
int temp = nums[tempIndex];
nums[tempIndex] = nums[tempIndex-1];
nums[tempIndex-1] = temp;
tempIndex--;
}
}
return nums;
}
Tips:当然，中间的while循环也可以使用for循环来代替
归并排序
归并排序会把序列分成长度相同的两个子序列，当无法往下分时候，就对子序列进行归并，也就是把两个排好序的子序列合并成一个有序序列，该操作会一直重复执行，直到所有的子序列都归并成一个整体为止。
合并两个排序好的子序列的时候，只需要维护两个指针从首位开始，逐步向后走就好了。所以归并排序的时间复杂度为O(n log n)。
代码如下：
public int[] sort(int[] nums) {
if (nums.length <= 1) {
return nums;
}
int len = nums.length;
int[] leftNums = new int[len / 2];
int[] rightNums = new int[len - len / 2];
System.arraycopy(nums, 0, leftNums, 0, len / 2);
System.arraycopy(nums, len / 2, rightNums, 0, len - len / 2);
if (leftNums.length != 1) {
leftNums = sort(leftNums);
}
if (rightNums.length != 1) {
rightNums = sort(rightNums);
}
return merge(leftNums, rightNums);
}
private int[] merge(int[] nums1, int[] nums2) {
if (nums1 == null || nums1.length == 0) return nums2;
if (nums2 == null || nums2.length == 0) return nums1;
int a = 0, b = 0;
int len1 = nums1.length, len2 = nums2.length;
int[] res = new int[len1 + len2];
int index = 0;
while (a < len1 && b < len2) {
int aNum = nums1[a];
int bNum = nums2[b];
if (aNum < bNum) {
res[index] = aNum;
a++;
} else {
res[index] = bNum;
b++;
}
index++;
}
if (a == len1) {
System.arraycopy(nums2, b, res, index, len1+len2-index);
} else {
System.arraycopy(nums1, a, res, index, len1+len2-index);
}
return res;
}
快速排序
快速排序算法首先会在序列中随机选择一个基准值，然后将除了基准值以外的数分为比基准值大的数和比基准值小的数，将小的数放基准值前面，将大的放后边，然后再将里面的数按照同样的方法排序。快速排序也是一种分治法。快速排序的时间复杂度为O(n long n)。
代码如下：
public int[] sort(int[] nums) {
sort(nums,0,nums.length-1);
return nums;
}
private void sort(int[] nums, int startIndex, int endIndex) {
if (endIndex <= startIndex) {
return;
}
int partiIndex = partitionV2(nums, startIndex, endIndex);
sort(nums, startIndex, partiIndex-1);
sort(nums, partiIndex+1, endIndex);
}
// 单边扫描
private int partition(int[] nums, int startIndex, int endIndex) {
// 随机取一个为基准值
Random r = new Random();
int rand = startIndex + r.nextInt(endIndex-startIndex);
swap(nums, startIndex, rand);
int res = startIndex;
int pivot = nums[startIndex];
for (int i = startIndex+1; i <= endIndex; i++) {
if (nums[i] < pivot) {
res++;
swap(nums, res, i);
}
}
// 在循环过程中，指针一直指向最后一个比基准值小的元素
// 调换基准和当前指针的数值
swap(nums, startIndex, res);
return res;
}
// 双边扫描
private int partitionV2(int[] nums, int startIndex, int endIndex) {
// 随机取一个为基准值
Random r = new Random();
int rand = startIndex + r.nextInt(endIndex-startIndex);
swap(nums, startIndex, rand);
int pivot = nums[startIndex];
int left = startIndex+1,right = endIndex;
while(left <= right) {
if (nums[left] > pivot && nums[right] < pivot) {
swap(nums, left, right);
left++;
right--;
continue;
}
if (nums[left] < pivot) {
left++;
continue;
}
if (nums[right] > pivot) {
right--;
continue;
}
left++;
right--;
}
swap(nums, startIndex, right);
return right;
}
private void swap(int[] nums, int startIndex, int endIndex) {
int temp = nums[startIndex];
nums[startIndex] = nums[endIndex];
nums[endIndex] = temp;
}
Tips:两种扫描方式均可，随机数作为基准。
当然还有其他一些排序，希尔排序、计数排序、稳定排序、桶排序、基数排序等，他们在某些固定的场合非常有效，我们可以根据使用场景来选择使用效率更高的排序方法。