题目描述：
给你一个整数数组?nums，请你将该数组升序排列。
题目解析（冒泡排序）：
从第一个数开始，逐个与后面的数进行比较，若该数大于后面的数则和后面的数进行位置交换，这样就可以确保在第一次循环后，位于数组最后的是最大的数，同理，然后在len-1的子数组上重复操作，将第二大的数放到倒数第二的位置上，一直这样下去，直到只剩两个数进行交换判断，即可完成整个数组的排序，代码如下：
// 冒泡排序 O(N^ 2) O(1)
class Solution {
public int[] sortArray(int[] nums) {
int len = nums.length;
for(int i = 0 ; i<len-1 ; i++){
for(int j = 0; j<len-i-1 ; j++){
if(nums[j]>=nums[j+1]){
nums[j] ^= nums[j+1];
nums[j+1] ^= nums[j];
nums[j] ^= nums[j+1];
}
}
}
return nums;
}
}
时间复杂度为O(N^2)，空间复杂度为O(1)，导致程序运行时间超时。
题目解析（选择排序）：
从未排序的数中选出最小的数，将其放置到已经排好序的数列后，重复操作即可实现数列的升序排列，代码如下：
// 选择排序 O(N^ 2) O(1)
class Solution {
public int[] sortArray(int[] nums) {
int len = nums.length;
for(int i = 0 ; i<len ; i++){
int pos = i;
for(int j = i ; j<len ; j++){
if(nums[pos]>nums[j])pos = j;
}
if(pos!=i){
nums[i] ^= nums[pos];
nums[pos] ^= nums[i];
nums[i] ^= nums[pos];
}
}
return nums;
}
}
时间复杂度为O(N^2)，空间复杂度为O(1)，导致程序运行时间超时。
题目解析（插入排序）：
插入排序类似于打麻将，我们只需要遍历数组，该目前的数按大小插入到该数前面的子数组中即可，怎么按大小插入呢，while循环往回看，直到找到第一个数小于目前的数，那么将该数放这个数后即可，若找完了仍然没有找到，则将该数放着整个数组的开头位置，代码如下：
// 插入排序 打麻将 O(N^ 2) O(1)
class Solution {
public int[] sortArray(int[] nums) {
int len = nums.length;
for(int i = 1 ; i<len ; i++){
int done = i-1;
int cur = -1;
for(int j = 0; j<=done; j++){
if(nums[j]>nums[i]){
cur = j;
break;
}
}
if(cur!=-1){
int temp = nums[i];
for(int j = done; j>=cur; j--){
nums[j+1] = nums[j];
}
nums[cur] = temp;
}
}
return nums;
}
}
时间复杂度为O(N^2)，空间复杂度为O(1)，导致程序运行时间超时。
题目解析（快速排序）：
快速排序涉及到了对于基准数的选择，通常情况下，我们一般选择数字开头的数字作为基准数，那么选择了基准数过后应该怎么进行排序呢，我用文字的形式大概说明一下。比如数组 [12，49，23，11，47，89，63]。选取基准数为47，首先我们需要将47与数组的末位数字进行交换得到[12，49，23，11，63，89，47]，将指针pos指向-1的位置，将index指向0的位置，开始的时候判断index指向的数是否小于等于我们选择的基准数，如果是，那么pos++, 判断i是否大于pos，若大于则交换pos和i指向的两个数，这里明显不成立，则i++进入下一个循环；然后pos=0 i=1，再进行判断，i++；i=2此时指向的数字23小于基准数47，则将pos++, pos=1, 交换两个数，得到数组[12，23，49，11，63，89，47]，计算到最后得到数组[12，23，11，47，49，63，89]，然后以同样的方式处理基准数左边的子数组和右边的子数组，直到，子数组的长度只有1为止，即可实现数组排序，代码如下：
// 快速排序 O(NLogN) O(logN)
class Solution {
public int[] sortArray(int[] nums) {
return sort(nums,0,nums.length-1);
}
int[] sort(int[] nums, int sta, int end){
if(nums.length<1||sta<0||end>=nums.length||sta>end)return null;
int pos = part(nums,sta,end);
if(pos>sta)sort(nums,sta,pos-1);
if(pos<end)sort(nums,pos+1,end);
return nums;
}
int part(int[] nums, int sta, int end){
if(sta==end)return sta;
int index = sta;
int temp = nums[sta];
nums[index] ^= nums[end];
nums[end] ^= nums[index];
nums[index] ^= nums[end];
int pos = sta-1;
for(int i = sta; i<=end ; i++){
if(nums[i]<=temp){
pos++;
if(i>pos){
nums[pos] ^= nums[i];
nums[i] ^= nums[pos];
nums[pos] ^= nums[i];
}
}
}
return pos;
}
}
时间复杂度为O(NLogN)，空间复杂度为O(LogN)，导致程序运行时间超时，一般情况下，在子数组的长度较小时，比如小于15时，可换做插入排序来提高程序的运行效率。
题目解析（希尔排序）：
类似于插入排序，只不过将其按gap分为了很多个组，通常来说，我们取gap初值为数组长度的一半，在每次循环后，将其赋值为当前值的1/2即可，直到gap=0。从1开始增长，然后以gap为间距判断与之前的子数组的大小关系，起始原理和插入排序一样，只不过引入了gap数值，代码如下：
// 希尔排序 O(NLogN)~O(N^ 2) O(1)
class Solution {
public int[] sortArray(int[] nums) {
int len = nums.length;
int gap = len/2;
while(gap>0){
for(int i = gap ; i<len ; i++){
int done = i-gap;
int cur = nums[i];
while(done>=0&&nums[done]>cur){
nums[done+gap] = nums[done];
done-=gap;
}
nums[done+gap] = cur;
}
gap/=2;
}
return nums;
}
}
时间复杂度为O(NLogN)~O(N^2)，空间复杂度为O(1)。
执行用时：26 ms, 在所有?Java?提交中击败了38.35%的用户
内存消耗：51.1 MB, 在所有?Java?提交中击败了40.69%的用户
题目解析（归并排序）：
将数组从中间分为两个数组，假设两个数组已经按从小到大的序列排好了，只需要使用一个双指针，将两个数组合并就可。那么怎么将这两个子数组排序呢，只需要将子数组继续再细分即可，直到数组内只有一个值，使用递归进行计算即可，代码如下：
// 归并排序 O(NLogN) O(N)
class Solution {
public int[] sortArray(int[] nums) {
if(nums.length<2)return nums;
int mid = nums.length/2;
int[] left = Arrays.copyOfRange(nums,0,mid);
int[] right = Arrays.copyOfRange(nums,mid,nums.length);
return merge(sortArray(left),sortArray(right));
}
int[] merge(int[] left, int[] right){
int l = 0, r = 0,pos = 0;
int[] ans = new int[left.length+right.length];
while(pos<ans.length){
if(l==left.length){
ans[pos++] = right[r++];
continue;
}
if(r==right.length){
ans[pos++] = left[l++];
continue;
}
if(left[l]<=right[r]){
ans[pos++] = left[l++];
}
else{
ans[pos++] = right[r++];
}
}
return ans;
}
}
时间复杂度为O(NLogN)，空间复杂度为O(N)。
执行用时：29 ms, 在所有?Java?提交中击败了37.14%的用户
内存消耗：51.4 MB, 在所有?Java?提交中击败了32.90%的用户
题目解析（堆排序）：
将一个数组排列为二叉堆来进行排序，首先我们需要使用一个函数来将一个数组生成二叉堆，根据完全二叉树的概念，数组长度除2减1对应的数值为最后一个不是叶子结点的结点，然后根据完全二叉树的概念，这个数之前的数同样符合，依次对其进行调整，怎么调整呢，只需要判断该值的左结点的数是不是大于该数，则将index指向左，然后判断右子结点，如果右子结点的数大于根结点和左子结点那么index指向右，然后将根结点同index交换即可，然后再将index指向结点作为根结点进行调整，怎么排序呢，只要每次将根结点取出（最大值），然后将最后一个结点（最小值）放置于根结点，再对根结点进行调整即可，直到树的长度为0，代码如下：
// 堆排序 O(NLogN) O(1)
class Solution {
int len;
public int[] sortArray(int[] nums) {
len = nums.length;
if(len<=1)return nums;
buildheap(nums);
while(len>1){
nums[0] ^= nums[len-1];
nums[len-1] ^= nums[0];
nums[0] ^= nums[len-1];
len--;
adjust(nums,0);
}
return nums;
}
void buildheap(int[] nums){
int cur = len/2-1;
for(int i = cur; i>=0 ; i--){
adjust(nums,i);
}
}
void adjust(int[] nums, int pos){
int l = pos*2+1, r = (pos+1)*2;
int index = pos;
if(l<len&&nums[l]>nums[pos])index = l;
if(r<len&&nums[r]>nums[pos]&&nums[r]>nums[l])index = r;
if(index!=pos){
nums[pos] ^= nums[index];
nums[index] ^= nums[pos];
nums[pos] ^= nums[index];
adjust(nums,index);
}
}
}
时间复杂度为O(NLogN)，空间复杂度为O(1)。
执行用时：29 ms, 在所有?Java?提交中击败了37.14%的用户
内存消耗：51.4 MB, 在所有?Java?提交中击败了32.90%的用户
题目解析（计数排序）：
使用一个数组来记录每个数字的个数，比如出现了两个3，那么在序号3处存放数值2，遍历数组来进行排序即可，代码如下：
// 计数排序 O(N+k) O(k)
class Solution {
public int[] sortArray(int[] nums) {
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i = 0; i<nums.length ; i++){
max = Math.max(max,nums[i]);
min = Math.min(min,nums[i]);
map.put(nums[i],map.getOrDefault(nums[i],0)+1);
}
int[] data = new int[max-min+1];
for(int key : map.keySet()){
data[key-min]+=map.get(key);
}
int pos = 0;
for(int i = 0 ; i<nums.length ;){
while(data[pos]!=0){
nums[i++] = pos+min;
data[pos]--;
}
pos++;
}
return nums;
}
}
时间复杂度为O(N+k)，空间复杂度为O(k)。
执行用时：30 ms, 在所有?Java?提交中击败了36.90%的用户
内存消耗：49.7 MB, 在所有?Java?提交中击败了97.16%的用户
题目解析（桶排序）：
将整个数组的范围分为某几个指定范围，将对应范围的数值存入到该范围的链表中去，将每个范围中的数值进行排序，然后整合输出即可，代码如下：
// 桶排序 O(N+c) O(n+k)
class Solution {
public int[] sortArray(int[] nums) {
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0; i<nums.length ; i++){
max = Math.max(max,nums[i]);
min = Math.min(min,nums[i]);
}
int num = (max-min)/10+1;
ArrayList<ArrayList<Integer>> list = new ArrayList<>(num);
for(int i = 0; i<num ; i++){
list.add(new ArrayList<Integer>());
}
for(int i = 0 ; i<nums.length ; i++){
list.get((nums[i]-min)/10).add(nums[i]);
}
int pos = 0;
for(int i = 0 ; i<num ; i++){
list.get(i).sort(Comparator.naturalOrder());
for(int j = 0 ; j<list.get(i).size() ; j++){
nums[pos++] = list.get(i).get(j);
}
}
return nums;
}
}
时间复杂度为O(N+c)，空间复杂度为O(N+k)。
执行用时：18 ms, 在所有?Java?提交中击败了50.13%的用户
内存消耗：51.6 MB, 在所有?Java?提交中击败了30.11%的用户
题目解析（基数排序）：
分为十个堆，代表不同数字位数的对应情况，先将数组按照个位存进行，然后按堆进行输出后，按十位存进去再输出，直到将数字的最高位存进去进行输出即可，这里有一个比较麻烦的，针对于存在负数的情况，有点难处理，我用了二十个堆，将负数和正数都存进去，再输出，这时候正数是排好的，负数都存在于前半部分，这时候我将负数转为整数，使用十个堆再进行处理，转为负数，逆向输出即可，代码如下：
// 基数排序 O(N*k) O(N+k)
class Solution {
public int[] sortArray(int[] nums) {
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0 ; i<nums.length ; i++){
max = Math.max(max,nums[i]);
min = Math.min(min,nums[i]);
}
min = -min;
int maxdigit = 0;
int mindigit = 0;
while(max>0){
maxdigit++;
max/=10;
}
while(min>0){
mindigit++;
min/=10;
}
ArrayList<ArrayList<Integer>> list = new ArrayList<>(20);
for(int i = 0 ; i<20 ; i++){
list.add(new ArrayList<Integer>());
}
for(int j = 0 ; j<maxdigit ; j++){
for(int k = 0 ; k<nums.length ; k++){
int cur = (nums[k]/(int)(Math.pow(10,j)))%10+10;
list.get(cur).add(nums[k]);
}
int pos = 0;
for(int k = 0; k<20 ; k++){
for(int q = 0; q<list.get(k).size(); q++){
nums[pos++] = list.get(k).get(q);
}
list.get(k).clear();
}
}
int pos = -1;
for(int i =0 ; i<nums.length ; i++){
if(nums[i]>=0)break;
pos++;
}
if(pos!=-1){
list.clear();
int[] med = new int[pos+1];
for(int i = 0 ; i<=pos ; i++){
med[i] = -nums[i];
}
for(int i = 0 ; i<10 ; i++){
list.add(new ArrayList<Integer>());
}
for(int j = 0 ; j<mindigit ; j++){
for(int k = 0 ; k<=pos ; k++){
int cur = (med[k]/(int)(Math.pow(10,j)))%10;
list.get(cur).add(med[k]);
}
int index = 0;
for(int k = 0; k<10 ; k++){
for(int q = 0; q<list.get(k).size(); q++){
med[index++] = list.get(k).get(q);;
}
list.get(k).clear();
}
}
for(int i = pos; i>=0 ; i--){
nums[pos-i] = -med[i];
}
}
return nums;
}
}
时间复杂度为O(N*k)，空间复杂度为O(N+k)。
执行用时：62 ms, 在所有?Java?提交中击败了34.54%的用户
内存消耗：52.2 MB, 在所有?Java?提交中击败了27.74%的用户
|