文章目录
八大排序冒泡排序直接插入排序选择排序快速排序
八大排序
当我们需求将一个无序序列的元素进行排序，使其成为一个元素有序的序列，我们会用到集中常用的排序算法。其中有八种经典排序算法：
冒泡排序快速排序直接选择排序堆排序直接插入排序希尔排序归并排序基数排序
这些不同的排序算法原理不同，但效果都是将一个无序的序列转换为元素有序。接下来我们介绍其中的几种排序思想。
准备工作： 因为排序算法中基本都会用到变量互换，所以我们先创建一个工具类Exchange，在类中创建一个静态方法exchange用于两个变量的互换。
冒泡排序
基本思想：数组元素两两比较，元素大的往后放，经过一轮比较后，最大元素就会出现在最后面。
Java实现：
public class BubbleSort{
public static int
[] bubbleSort(int
[] arr
){
for (int i
= 0; i
< arr
.length
-1; i
++) {
for (int j
=0;j
<arr
.length
-1-i
;j
++){
if (arr
[j
]>arr
[j
+1]){
Exchange
.exchange(arr
,j
,j
+1);
}
}
}
return arr
;
}
}
测试： 定义一个数组{1314,30,50,25,5,-15,105,2000}调用 bubbleSort 方法进行冒泡排序。 】
直接插入排序
基本思想：每次把后面一个元素插入到前面的一个有序序列中，使之仍保持有序。Java实现：
public class InsertSort {
public static int
[] insertSort(int
[] arr
){
for (int i
= 1; i
< arr
.length
; i
++) {
int j
=i
;
while (j
>0&&arr
[j
]<arr
[j
-1]){
Exchange
.exchange(arr
,j
,j
-1);
j
--;
}
}
return arr
;
}
}
测试： 定义一个数组{1314,30,50,25,5,-15,105,2000}调用 insertSort 方法进行直接插入排序。
选择排序
基本思想：每次拿一个元素跟后面的元素挨个比较，小的往前换，经过一轮比较，最小元素就会出现在最前面。Java实现：
public class SelectSort {
public static int
[] selectSort(int
[] arr
){
for (int i
= 0; i
< arr
.length
-1; i
++) {
for (int j
= 1+i
; j
< arr
.length
; j
++) {
if (arr
[i
]>arr
[j
]){
Exchange
.exchange(arr
,i
,j
);
}
}
}
return arr
;
}
}
测试： 定义一个数组{1314,30,50,25,5,-15,105,2000}调用 selectSort 方法进行选择排序。
快速排序
基本思想：
将基准数挖出形成第一个坑。由后向前找比他小的数，找到后挖出此数填到前一个坑中。由前向后找比他大或等于的数，找到后也挖出此数填到前一个坑中。再重复执行2，3两步骤。
Java实现：
public class quickSort {
public static void quickSort(int
[] arr
,int start
,int end
){
if (start
<end
){
int index
=getIndex(arr
,start
,end
);
quickSort(arr
,start
,index
-1);
quickSort(arr
,index
+1,end
);
}
}
private static int
getIndex(int
[] arr
,int start
,int end
){
int t
=arr
[start
];
while (start
<end
){
while (start
<end
&&arr
[end
]>=t
){
end
--;
}
if (start
<end
){
arr
[start
]=arr
[end
];
start
++;
}
while (start
<end
&&arr
[start
]>t
){
start
++;
}
if (start
<end
){
arr
[end
]=arr
[start
];
end
--;
}
}
arr
[start
]=t
;
return start
;
}
}
测试： 定义一个数组{1314,30,50,25,5,-15,105,2000}调用 quickSort 方法进行选择排序。
