题目

描述

• 给定一个数组，请你编写一个函数，返回该数组排序后的形式。

方法一

思路

• 题目要求对数组进行升序排序，可以使用冒泡排序来对数组进行排序。

具体步骤

• 1.循环遍历找出第i小的值，并将其置于第i位；
• 2.当不发生交换时，数组有序，循环终止；
• 代码如下：

  import java.util.*;
  public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        for (int i = 0;i < arr.length;++i){
            // 表示本次冒泡是否发生交换
            boolean flag = false;
            for (int j = arr.length-1;j > i;--j){
                if (arr[j-1] > arr[j]){
                    int temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                    flag = true;
                }
            }
            // 未发生交换，已经有序
            if (!flag){
                break;
            }
        }
        return arr;
    }
  }

• 时间复杂度：,比较次数 = n(n-1)/2,移动次数 = 3n(n-1)/2,所以时间复杂度为；
• 空间复杂度：，常数级空间复杂度。

方法二

思路

• 方法一运行超时，的时间复杂度无法完美解决问题，那么就考虑使用的排序算法，就选与冒泡排序属于同一类的快速排序吧。
• 介绍一下快速排序：快速排序的基本思想是基于分治法的，在待排序数组arr中任取一个元素i，作为基准，通过一趟排序将待排序数组划分为两个独立的部分arr[0,k-1]（所有元素小于i）,arr[k+1,n]（所有元素大于i），i放在arr[k]上，这是一次快排。接着，再对两个子数组进行递归快排即可。

具体步骤

• 参考下图示例：
  
• 代码如下：

  import java.util.*;
  public class Solution {
  /**
  * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
  * 将给定数组排序
  * @param arr int整型一维数组 待排序的数组
  * @return int整型一维数组
  */
  public int[] MySort (int[] arr) {
     // write code here
     quickSort(arr,0,arr.length-1);
     return arr;
  }
  private void quickSort(int[] arr,int low,int high){
     if (low < high){
         // 划分为两个子数组
         int pivotpos = partition(arr,low,high);
         // 递归快排
         quickSort(arr,low,pivotpos-1);
         quickSort(arr,pivotpos+1,high);
     }
  }
  private int partition(int[] arr,int low,int high){
     // 默认取最低位
     int pivot = arr[low];
     while(low < high){
         while(low < high && arr[high] >= pivot)
             --high;
         // 将比基准小的值移到左端
         arr[low] = arr[high];
         while(low < high && arr[low] <= pivot)
             ++low;
         // 将比基准大的值移到右端
         arr[high] = arr[low];
     }
     arr[low] = pivot;
     return low;
  }
  }

• 时间复杂度：,当数组基本有序或者基本逆序时，最坏时间复杂度为，而平均时间复杂度为。
• 空间复杂度：，最坏情况下需要进行n-1次递归调用，所以是。