题目
给你一个整数数组 nums，将该数组升序排列。
示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
提示：
1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000
解题
1.选择排序
这种排序方式应该是很简单的，容易理解，对于长度为n的数组，遍历n-1次，每次在无序的数组段中选择最小的一个元素和无序数组第一个元素交换位置。或者反过来，找最大的和最后一个交换，也是一样的。在交换过程中，相同元素的位置不会变化，因此是稳定的。不过判断的方式不同，导致的稳定性也不同。比如如果我写成nums[j]<=nums[min]，那就变成不稳定的了。
时间复杂度是O(n^2)
//选择排序
public void selectSort(int[] arr){
int min = 0;
int minIndex = 0;
for(int k=0;k<arr.length-1;k++){
min = arr[k];
minIndex = k;
for(int i=k+1;i<=arr.length-1;i++){
if(min>arr[i]){
min = arr[i];
minIndex = i;
}
}
if(minIndex >k){
arr[minIndex] = arr[k];
arr[k]=min;
}
System.out.println("第"+(k+1)+"轮排序的结果为:"+ Arrays.toString(arr));
}
}
2.冒泡排序
这种排序方式是对一个数组遍历n-1次，每次通过交换相邻两个元素位置，使得局部相对大小满足要求，每次的结果是将最大值交换到了最后位置，就像泡泡冒到最高一样。
时间复杂度是O(n^2)，稳定的。
public void bubbleSort(int[] arr){
int temp=0;
boolean flag = false;
for(int i=0;i<arr.length-1;j++){
for(int j=0;j<arr.length-1-i;j++){
if(arr[j]>arr[j+1]){
flag = true;
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
if(flag){
flag = false;
}else{
break;
}
}
}
3.插入排序
模拟一个插入元素的过程，在插入的过程中要找到插入的位置，使得插入之后新的数组段是有序的。在查找位置的时候，也要从后往前去遍历，因此时间复杂度也是比较高，O(n^2)，稳定的。
public static void insertSort(int[] arr){
for(int i=1;i<=arr.lenght()-1;i++){
int insertVal = arr[i];
int preIndex = i-1;
while(preIndex>=0 && insertVal<arr[preIndex]){
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
if(preIndex+1!=i){
arr[preIndex+1]=insertVal;
}
}
}
4.希尔排序
希尔排序是插入排序的优化，将插入排序的比较间隔扩大，不再是相邻元素比较大小，比插入排序优化了一些，时间复杂度O(n^1.3-2)，因为交换的时候是跳跃式的交换，无法保证稳定，不稳定的。
public void shellSort(int[] arr ) {
int count=0;
int preIndex =0;
int insertVal=0;
for(int gap=arr.length/2;gap>0;gap=gap/2){
for(int i=gap;i<arr.length;i++){
preIndex = i-gap;
insertVal = arr[i];
if(insertVal<arr[preIndex]){
while(preIndex>=0 && insertVal<arr[preIndex]){
arr[preIndex+gap] = arr[preIndex];
preIndex=preIndex-gap;
}
arr[preIndex+gap]=insertVal;
}
}
System.out.println("第"+(++count)+"轮排序结果："+ Arrays.toString(arr));
}
}
5.快速排序
快速排序有多种实现方式，这里主要给出两种比较常用的，分别适合于不同的应用场景。时间复杂度O(nlogn)，因为交换元素无法保证顺序，是不稳定的。
第一种实现，左右双指针，交换逆序元素。
先选择一个标杆元素（通常是用第一个元素）。执行：
从右向左遍历找到第一个小于标杆的值，从左向右遍历找到第一个大于标杆的值，这两个位置的值是不满足顺序要求的，交换他们的值。
然后重复上面的过程。知道左右指针位置相同，将标杆元素和指针交换，此时数组分为两部分，然后递归进行排序。
注意：在一些情况下，不需要我们进行完全的排序，只需要将数组分为两部分相对有序，如查找中位数，就是将数组分为长度相同的但是大小分开的两个子数组，此时我们不需要完全排序，只需要执行上面的过程，能够降低时间复杂度。
public static void quickSort(int[] arr, int left, int right) {
if (left > right) {
return;
}
int pivot = arr[left];
int i = left;
int j = right;
while (i != j) {
//先从右边开始往左找，直到找到比pivot值小的数
while (arr[j] >= pivot && i < j) {
j--;
}
//先从左边开始往左找，直到找到比pivot值大的数
while (arr[i] <= pivot && i < j) {
i++;
}
// 找到左边比中轴大，右边比中轴小的数，交换两个数在数组中的位置
if (i < j) {
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
// 将基准数放到中间的位置（基准数归位）
arr[left] = arr[i];
arr[i] = pivot;
// 递归，继续向基准的左右两边执行和上面同样的操作
sort(arr, left, i - 1);
sort(arr, i + 1, right);
}
第二种实现：两个伴随指针
在数组排序时，采用第一种实现是可以的，但是如果是对链表排序时，无法用指针随机访问每个位置，只能从链表头部从前往后遍历，此时可以采用第二种实现。
先确定一个标杆值，通常是第一个值。用两个指针，指针i和指针j，指针j用于遍历，指针i用于记录小于标杆值的边界，当j找到一个小于标杆的值时，将i和j交换，并将i向右移动，这样就能保证，遍历结束时，i左边都是小于标杆值的，右边都是大于的。
public static void quickSort(int[] nums,int begin, int end){
if(begin>end||begin==end){
return;
}
int i=begin+1;
int j=begin+1;
int target=nums[begin];
while(j<=end){
if(nums[j]<target){
swap(nums,i,j);
i++;
j++;
}else{
j++;
}
}
swap(nums,begin,--i);
quickSort(nums,begin,i-1);
quickSort(nums,i+1,end);
}
6.归并排序
这种排序方式采用分治的思想，将原数组先拆分成小数组，分别排序之后，再将相邻的有序数组合并，还是比较好理解的。
一共拆分为logn层，每个层合并的过程O(n)，因此是O(nlogn)，可以保证稳定。
public static int[] mergeSort(int[] nums, int begin, int end){
if(begin>end){
return new int[0];
}
if(begin==end){
return new int[]{nums[begin]};
}
int m=begin+(end-begin)/2;
int[] lres=mergeSort(nums,begin,m);//拆分为小数组，排序
int[] rres=mergeSort(nums,m+1,end);
//下面来进行合并
int[] res=new int[lres.length+rres.length];
int i=0;
int j=0;
int index=0;
while(i<lres.length&&j<rres.length){
if(lres[i]<=rres[j]){
res[index++]=lres[i++];
}else{
res[index++]=rres[j++];
}
}
while(i<lres.length){
res[index++]=lres[i++];
}
while(j<rres.length){
res[index++]=rres[j++];
}
return res;
}
9.基数排序
基数排序 是将整数按位数切割成不同的数字，然后按每个位数分别比较从而得到有序的序列。
public static void radixSort(int[] arr) {
//得到数组中最大的数的位数
int maxNum = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > maxNum) {
maxNum = arr[i];
}
}
//得到最大数是几位数
int maxLength = (maxNum + "").length();
//定义一个二维数组，表示10个桶, 每个桶就是一个一维数组
int[][] bucket = new int[10][arr.length];
//每个桶存入了几个数字
int[] everyBucketNum = new int[10];
// n* = 10 的原因是
//123取出个位数字是 123 % 10，即 123 / 1 %10
//123 取出十位数字是123 / 10 % 10;
//123 去除百位数字是123 /100 % 10
//以此类推
for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
for (int j = 0; j < arr.length; j++) {
//取出每个元素的对应位的值
int digit = arr[j] / n % 10;
//放入到对应的桶中
bucket[digit][everyBucketNum[digit]] = arr[j];
everyBucketNum[digit]++;
}
//按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
int index = 0;
//遍历每一桶，并将桶中是数据，放入到原数组
for (int k = 0; k < everyBucketNum.length; k++) {
if (everyBucketNum[k] != 0) {
for (int l = 0; l < everyBucketNum[k]; l++) {
arr[index++] = bucket[k][l];
}
}
//放回原数组后，需要将每个 everyBucketNum[k] = 0
everyBucketNum[k] = 0;
}
System.out.println("第" + (i + 1) + "轮，对个位的排序处理 arr =" + Arrays.toString(arr));
}
}
7.堆排序
堆排序写起来可能比较麻烦一些，基于数组的堆排序还是稍微简单的，如果是基于节点的就更麻烦了。
堆排序的主要操作包括建堆，调整等。
建堆是将原始数组建成一个大顶堆或者小顶堆，调整是在排序过程中，将最大值或最小值拿掉之后，剩下的元素进行调整。
建堆的时间复杂度是O(nlogn)，排序的时间复杂度是O(nlogn)，无法保证稳定性。
//堆排序
public static int[] heapSort(int[] nums) {
buildHeap(nums);//建堆
int size=nums.length;
for(int i=0;i<nums.length-1;i++){
swap(nums,0,size-1);//得到最大元素
size--;
adjust(nums,0,size);//调整堆
}
return nums;
}
//建一个大顶堆
public static void buildHeap(int[] arr){
for(int i=1;i<arr.length;i++){
insert(arr,i);
}
System.out.println(Arrays.toString(arr));
}
//向堆中插入元素
public static void insert(int[] arr,int index){
int parent=0;
while(index!=0){//根节点是没有父节点的
parent=(index-1)/2;
if(arr[parent]<arr[index]){
swap(arr,parent,index);
}
index=parent;
}
}
//从index开始调整大顶堆
public static void adjust(int[] arr, int index, int size){
int left=index*2+1;
int right=index*2+2;
int max=index;
while(left<size){
if(arr[left]>arr[max]){
max=left;
}
if(right<size&&arr[right]>arr[max]){
max=right;
}
if(max!=index){
swap(arr,max,index);
}else{
break;
}
index=max;
left=index*2+1;
right=index*2+2;
}
}
8.桶排序
桶排序的思想其实是用空间换时间，在重复元素比较多的时候用桶排序能够比较快，首先找到数组中元素的范围，在范围内设置不同的桶计数每个范围内数字的个数，然后基于桶来排序。
时间复杂度O(n)，通常的比较排序最优的时间复杂度不超过O(nlogn)，但是桶排序可以，计数排序也可以。无法保证稳定。
public int[] bucketSort(int[] nums){
if(nums==null||nums.length==0){
return nums;
}
int low= Integer.MAX_VALUE;
int high=Integer.MIN_VALUE;
for(int i=0;i<nums.length;i++){
low=Math.min(low,nums[i]);
high=Math.max(high,nums[i]);
}
int n=high-low+1;
int[] buckets=new int[n];//准备了最多数量的桶，每个值对应一个
for(int t:nums){
buckets[t-low]++;
}
int[] res=new int[nums.length];
int index=0;
for(int i=0;i<n;i++){
for(int j=0;j<buckets[i];j++){
res[index++]=low+i;
}
}
return res;
}
网友评论