- 调用库函数Arrays.sort
- 冒泡排序BubbleSort
- 快速排序QuickSort
- 归并排序MergeSort
- 堆排序HeapSort
- 优先级队列PriorityQueue
解法1：调用库函数Arrays.sort
import java.util.Arrays;
public class Solution {
public int[] MySort (int[] arr) {
//调用库函数sort；
Arrays.sort(arr);
return arr;
}
}解法2：冒泡排序BubbleSort
以升序排列为例：将第一个元素和第二个元素比较，若前者大于后者，则交换两者的位置，再将第二个元素与第三个元素比较，若前者大于后者则交换两者位置，以此类推直到倒数第二个元素与最后一个元素比较，若前者大于后者，则交换两者位置。这样一轮比较下来将会把序列中最大的元素移至序列末尾，这样就安排好了最大数的位置，接下来只需对剩下的（n-1）个元素，重复上述操作即可。
时间复杂度：
若原数组本身就是有序的（这是最好情况），仅需n-1次比较就可完成，时间复杂度依然为O(n）；
若是倒序，比较次数为 n-1+n-2+...+1=n(n-1)/2，交换次数和比较次数等值。所以，其时间复杂度依然为O(n2）
空间复杂度：
使用常数个辅助单元：O(1）
运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。
case通过率为20.00%
public int[] MySort (int[] arr) {
if(arr.length<2){
return arr;
}
// for(int end=arr.length-1; end>0; end--){//每次选出最大的放到最后，重复；
// for(int i=0;i<end;i++){
// if(arr[i]>arr[i+1]){
// swap(arr,i,i+1);
// }
// }
// }
for(int i=0;i<arr.length-1;i++){
for(int j=0;j<arr.length-i-1;j++){
if(arr[j]>arr[j+1]){
swap(arr,j,j+1);
}
}
}
return arr;
}
public void swap(int[]arr,int i, int j){
int tmp;
tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
/* public static void swap(int[] arr, int i, int j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
*/
解法3：快速排序QuickSort
快速排序(Quick Sort)：是对冒泡排序的一种改进方法，在冒泡排序中，进行元素的比较和交换是在相邻元素之间进行的，元素每次交换只能移动一个位置，所以比较次数和移动次数较多，效率相对较低。而在快速排序中，元素的比较和交换是从两端向中间进行的，较大的元素一轮就能够交换到后面的位置，而较小的元素一轮就能交换到前面的位置，元素每次移动的距离较远，所以比较次数和移动次数较少，y速度较快，故称为“快速排序”。
快速排序的基本思想是：
- 在待排序的元素任取一个元素作为基准(通常选第一个元素，但最的选择方法是从待排序元素中随机选取一个作为基准)，称为基准元素；
- 将待排序的元素进行分区，比基准元素大的元素放在它的右边，比其小的放在它的左边；
- 对左右两个分区重复以上步骤直到所有元素都是有序的
代码1：
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型一维数组 待排序的数组
* @return int整型一维数组
*/
public int[] MySort (int[] arr) {
quickSort(arr , 0 , arr.length-1);
return arr;
}
public void quickSort(int[] list, int left, int right) {
if (left < right) {
// 分割数组，找到分割点
int point = partition(list, left, right);
// 递归调用，对左子数组进行快速排序
quickSort(list, left, point - 1);
// 递归调用，对右子数组进行快速排序
quickSort(list, point + 1, right);
}
}
/**
* 分割数组，找到分割点
*/
public int partition(int[] list, int left, int right) {
// 用数组的第一个元素作为基准数
int first = list[left];
while (left < right) {
while (left < right && list[right] >= first) {
right--;
}
// 交换
swap(list, left, right);
while (left < right && list[left] <= first) {
left++;
}
// 交换
swap(list, left, right);
}
// 返回分割点所在的位置
return left;
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}代码2：
public static void quickSort(int[] arr,int L,int R){
if(L<R){
swap(arr,L+(int)(Math.random()*(R-L+1)),R);//加上就是随机快排, Math.random返回>=0，小于R-L+1的数
int [] p= paration(arr,L,R);
quickSort(arr,L,p[0]-1);
quickSort(arr,p[0]+1,R);
}
}
public static int[] paration(int[] arr,int L,int R){
int less=L-1;
int more=R;
int current=L;//current作为遍历数组的下标
while(current<more){
if(arr[current]<arr[R]){
swap(arr,++less,current++);
}
else if(arr[current]==arr[R]){
current++;
}
else{
swap(arr,--more,current);
}
}
swap(arr,more,R);
return new int[]{less+1,more};
}解法4：归并排序MergeSort
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 将给定数组排序 * @param arr int整型一维数组 待排序的数组 * @return int整型一维数组 */ public int[] MySort (int[] arr) { mergeSort(arr,0,arr.length-1); return arr; } public void mergeSort(int[] arr,int l,int r){ if(l==r){ return; } int mid = l+((r-l)>>1); //中点位置，即(l+r)/2 mergeSort(arr,l,mid); mergeSort(arr,mid+1,r); merge(arr,l,mid,r); } public void merge(int[] arr,int l,int mid,int r){ int [] help= new int[r-l+1]; //辅助数组 int i=0; int p1=l; //左半数组的下标 int p2=mid+1; //右半数组的下标 //判断是否越界 while(p1<=mid && p2<=r){ help[i++]=arr[p1]<arr[p2] ? arr[p1++] : arr[p2++]; } //p1没有越界，说明p2越界了，将左边剩余元素拷贝到辅助数组 while(p1<=mid){ help[i++]=arr[p1++]; } //p2没有越界，说明p1越界了 while(p2<=r){ help[i++]=arr[p2++]; } //将辅助数组元素拷贝会原数组 for(i=0;i<help.length;i++){ arr[l+i]=help[i]; } } }解法5：堆排序HeapSort
堆结构就是将一颗完全二叉树映射到数组中的一种存储方式
heapInsert和heapify
大根堆最重要的两个操作就是heapInsert和heapify，前者是当一个元素加入到大根堆时应该自底向上与其父结点比较，若大于父结点则交换；后者是当堆中某个结点的数值发生变化时，应不断向下与其孩子结点中的最大值比较，若小于则交换。下面是对应的代码：//判断该结点与父结点的大小，大结点一直往，建立大根堆 public static void heapInsert(int[] arr,int index){ while(arr[index]>arr[(index-1)/2]){ swap(arr,index,(index-1)/2); index=(index-1)/2; } } //一个值变小往下沉的过程 public static void heapify(int[] arr,int index,int size){ int left=index*2+1; while(left<size){ int largest = left + 1 < size && arr[left+1] > arr[left] ? left+1 : left; largest = arr[largest] > arr[index] ? largest :index; if(largest==index){ break; } swap(arr,largest,index); index=largest; left=index*2 +1; } }利用heapify排序
代码
public int[] MySort (int[] arr) { heapSort(arr); return arr; } public static void heapSort(int[] arr){ if(arr == null || arr.length<2){ return; } for(int i=0;i<arr.length;i++){ heapInsert(arr,i); //构造完全二叉树 } int size = arr.length; swap(arr,0,--size); while(size>0){ heapify(arr,0,size);// 最后一个数与根交换 swap(arr,0,--size); } } //判断该结点与父结点的大小，大结点一直往，建立大根堆 public static void heapInsert(int[] arr,int index){ while(arr[index]>arr[(index-1)/2]){ swap(arr,index,(index-1)/2); index=(index-1)/2; } } //一个值变小往下沉的过程 public static void heapify(int[] arr,int index,int size){ int left=index*2+1; while(left<size){ int largest = left + 1 < size && arr[left+1] > arr[left] ? left+1 : left; largest = arr[largest] > arr[index] ? largest :index; if(largest==index){ break; } swap(arr,largest,index); index=largest; left=index*2 +1; } } //交换函数 public static void swap(int[] arr, int i, int j){ int tmp; tmp=arr[i]; arr[i]=arr[j]; arr[j]=tmp; }解法6：优先级队列PriorityQueue
优先队列不再遵循先入先出的原则，而是分为两种情况：
最大优先队列，无论入队顺序，当前最大的元素优先出队；
最小优先队列，无论入队顺序，当前最小的元素优先出队；
比如有一个最大优先队列，它的最大元素是8，那么虽然元素8并不是队首元素，但出队的时候仍然让元素8首先出队：
优先级队列，也叫二叉堆、堆（不要和内存中的堆区搞混了，一个是内存区域，一个是数据结构）。
堆的本质上是一种完全二叉树，分为：小根堆：树中每个非叶子结点都不大于其左右孩子结点的值，也就是根节点最小的堆，图a
大根堆：树中每个非叶子结点都不小于其左右孩子结点的值，也就是根节点最大的堆，图b
public int[] MySort (int[] arr) { // PriorityQueue<Integer> queue=new PriorityQueue<Integer>(); PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>(){ public int compare(Integer a,Integer b){ return a.compareTo(b); } }); for(int i=0;i<arr.length;i++){ queue.add(arr[i]); } int[] newarr=new int[arr.length]; for(int i=0;i<arr.length;i++){ newarr[i]=queue.poll(); } return newarr; }
京公网安备 11010502036488号