文章目录
排序选择排序简介代码实现
冒泡排序简介代码实现
插入排序代码实现
归并排序简介代码实现
堆排序简介代码实现
快速排序简介代码实现
桶系列--(偷个懒)排序总结
排序
选择排序
简介
选择排序的排序方式：一个数组，我们假定长度为n，从头(索引为0)遍历，第一次，我从0 ~ n-1的数中挑出一个最小值放到0位置，第二次，我从1 ~ n-1的数中挑出一个最小值放到1位置，依此类推，一直到n-1位置结束，至此排序完成
代码实现
public class SelectSort {
public static void selectSort(int []arr
){
if (arr
==null
|| arr
.length
<=0){
return ;
}
for(int i
=0;i
<arr
.length
-1;i
++){
int minIndex
= i
;
for (int j
=i
+1;j
<arr
.length
;j
++){
minIndex
= arr
[minIndex
]>arr
[j
]?j
:minIndex
;
}
swap(arr
,minIndex
,i
);
}
}
public static void swap(int[] arr
, int i
, int j
) {
int tmp
= arr
[i
];
arr
[i
] = arr
[j
];
arr
[j
] = tmp
;
}
public static void main(String
[] args
) {
int []arr
= {5,4,2,3,1};
selectSort(arr
);
for (int i
: arr
) {
System
.out
.print(i
+" ");
}
}
}
冒泡排序
简介
冒泡排序的思想就是，我从头遍历，每次比较相邻的两个数，然后遍历一遍结束之后，最大值都放到最后。然后待排序子序列长度-1，继续从头遍历，重复上述过程。
代码实现
public class BubbleSort {
public static void bubbleSort(int []arr
){
if (arr
==null
|| arr
.length
<=0){
return;
}
for(int i
=0;i
<arr
.length
;i
++){
for (int j
=0;j
<arr
.length
-1-i
;j
++){
if (arr
[j
]>arr
[j
+1]){
int temp
= arr
[j
];
arr
[j
] = arr
[j
+1];
arr
[j
+1] = temp
;
}
}
}
}
public static void main(String
[] args
) {
int []arr
= {4,5,3,2,1};
bubbleSort(arr
);
for (int i
: arr
) {
System
.out
.print(i
+" ");
}
}
}
插入排序
插入排序的思想：我第一次保证0 ~ 0序列上有序，第二次保证0 ~ 1序列上有序，以此类推，到最后0 ~ n上有序。
代码实现
public class InsertSort {
public static void insertSort(int []arr
){
if (arr
==null
|| arr
.length
<=0){
return ;
}
for (int i
=1;i
<arr
.length
;i
++){
for (int j
=i
;j
>0 && arr
[j
]<arr
[j
-1];j
--){
swap(arr
,j
,j
-1);
}
}
}
public static void swap(int[] arr
, int i
, int j
) {
int tmp
= arr
[i
];
arr
[i
] = arr
[j
];
arr
[j
] = tmp
;
}
public static void main(String
[] args
) {
int []arr
= {5,4,2,3,1};
insertSort(arr
);
for (int i
: arr
) {
System
.out
.print(i
+" ");
}
}
}
归并排序
简介
归并排序的思想：先将数组分成左右两份，我先保证左右两份各是有序的，最后我再合并左右，保证整个是有序的。
代码实现
public class MergeSort {
public static void mergeSort(int []arr
){
if (arr
== null
|| arr
.length
<=0){
return ;
}
sort(arr
,0,arr
.length
-1);
}
private static void sort(int []arr
,int left
,int right
){
if (left
>= right
){
return;
}
int mid
= left
+((right
-left
)>>1);
sort(arr
,left
,mid
);
sort(arr
,mid
+1,right
);
merge(arr
,left
,mid
,right
);
}
private static void merge(int []arr
,int start
,int mid
,int end
){
int []temp
= new int[end
-start
+1];
int index
= 0;
int left
= start
;
int right
= mid
+1;
while(left
<=mid
&& right
<=end
){
temp
[index
++] = arr
[left
]>arr
[right
]?arr
[right
++]:arr
[left
++];
}
while(left
<=mid
){
temp
[index
++] = arr
[left
++];
}
while(right
<=end
){
temp
[index
++] = arr
[right
++];
}
for (int i
=0;i
<temp
.length
;i
++){
arr
[start
+i
] = temp
[i
];
}
}
public static void main(String
[] args
) {
int []arr
= {5,4,3,2,1};
mergeSort(arr
);
for (int i
: arr
) {
System
.out
.print(i
+" ");
}
}
}
堆排序
简介
堆排序思想：将数组想象成完全二叉树的样子，其实这就是堆。又分为大根堆小根堆。我先让数组中的元素建成堆，有效堆大小初始为数组大小，然后交换0和n-1，有效堆大小-1，然后将堆顶元素下沉，直到该元素的大小比子节点的元素都大，停止下沉，然后交换0和有效堆容量-1的元素，继续上述过程，最终有效堆大小为0，排序结束
代码实现
public class HeapSort {
public static void heapSort(int []arr
){
if (arr
== null
|| arr
.length
<=0){
return ;
}
for (int i
=arr
.length
-1;i
>=0;i
--){
heapify(arr
,i
,arr
.length
);
}
int size
= arr
.length
;
swap(arr
,0,--size
);
while(size
>0){
heapify(arr
,0,size
);
swap(arr
,0,--size
);
}
}
private static void heapInsert(int []arr
,int index
){
while(arr
[index
]>arr
[(index
-1)/2]){
swap(arr
,index
,(index
-1)/2);
index
= (index
-1)/2;
}
}
private static void heapify(int []arr
,int index
,int size
){
int left
= 2*index
+1;
while(left
<size
){
int largestIndex
= left
+1<size
&& arr
[left
]<arr
[left
+1]?left
+1:left
;
largestIndex
= arr
[largestIndex
]>arr
[index
]?largestIndex
:index
;
if (largestIndex
== index
){
break;
}
swap(arr
,largestIndex
,index
);
index
= largestIndex
;
left
= index
*2+1;
}
}
private static void swap(int []arr
,int i
,int j
){
int temp
= arr
[i
];
arr
[i
] = arr
[j
];
arr
[j
] = temp
;
}
public static void main(String
[] args
) {
int []arr
= {5,4,3,2,1};
heapSort(arr
);
for (int i
: arr
) {
System
.out
.print(i
+" ");
}
}
}
快速排序
简介
快速排序思想：我先随机在数组中挑一个元素，让它与最后一个元素做交换，然后在0-n-2的数组上做分区，把小于最后一个元素值的元素放在左边，将等于最后一个元素值的元素放中间，把大于最后一个元素值的元素放在右边，再将小于区域进行分区和大于区域进行分区，最终达到整个数组有序
代码实现
public class QuickSort {
public static void quickSort_1(int []arr
,int L
,int R
){
if (L
>= R
){
return ;
}
int partition
= arr
[R
];
int less
= L
-1;
int more
= R
+1;
int left
= L
;
while(left
< more
){
if (arr
[left
] > partition
){
swap(arr
,left
,--more
);
}else if (arr
[left
] == partition
){
left
++;
}else{
swap(arr
,left
++,++less
);
}
}
quickSort_1(arr
,L
,less
);
quickSort_1(arr
,more
,R
);
}
public static void quickSort_v2(int []arr
,int L
,int R
){
if (L
< R
){
swap(arr
,L
+(int)(Math
.random()*(R
-L
+1)),R
);
int []partition
= partition(arr
,L
,R
);
quickSort_v2(arr
,L
,partition
[0]-1);
quickSort_v2(arr
,partition
[1]+1,R
);
}
}
private static int[] partition(int []arr
,int L
,int R
){
int less
= L
-1;
int more
= R
;
while(L
< more
){
if (arr
[L
] < arr
[more
]){
swap(arr
,L
++,++less
);
}else if (arr
[L
] > arr
[more
]){
swap(arr
,L
,--more
);
}else{
L
++;
}
}
swap(arr
,more
,R
);
return new int[]{less
+1,more
};
}
private static void swap(int []arr
,int i
,int j
){
int temp
= arr
[i
];
arr
[i
] = arr
[j
];
arr
[j
] = temp
;
}
public static void main(String
[] args
) {
int [] arr
= {1,4,3,7,5,3};
quickSort_v2(arr
,0,arr
.length
-1);
for (int i
: arr
) {
System
.out
.print(i
+" ");
}
}
}
桶系列–(偷个懒)
排序总结
时间复杂度额外空间复杂度稳定性
选择排序O( n2 )O(1)×冒泡排序O(n2)O(1)√插入排序O(n2)O(1)√归并排序O(n*log(n))O(n)√堆排序O(n*log(n)O(1)×快速排序O(n*log(n))O(log(n))×
重要的是归并排序、堆排序和快速排序的选择，在排序当中，就看你想要什么，你想要稳定，就采用归并排序；想要时间快，就用快速排序，这里补充一点，快速排序的常数指标优于其它两个排序；想要追求缩小空间复杂度，就采用堆排序。 目前还没有时间复杂度好、空间复杂度低、稳定性好的排序。 工程上的排序选择就是，在排序数量小于60的时候采用插入排序，大于60采用快速排序 工程上就是考虑两个方面：
考虑O(nlogn)和O(n2)各自的优势稳定性的考虑
