各位看官早安午安晚安呀
如果您觉得这篇文章对您有帮助的话
欢迎您一键三连，小编尽全力做到更好
欢迎您分享给更多人哦
今天我们来学习七大排序算法
一：直接插入排序
直接插入排序是一种简单的插入排序法，其基本思想是：
把待排序的 逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到 一个新的有序序列 。实际中我们玩扑克牌时，就用了插入排序的思想。
/**
* 时间复杂度：最好：O(n)：本身就是有序的{1,2,3,4,5}
*
* 最坏 O(n^2):{5,4,3,2,1}
*
* 空间复杂度：O(1);(没有额外的申请空间)
*
* 稳定性：稳定的排序
*
* @param array
*/
public static void insertSort(int[] array){
for (int i = 1; i < array.length; i++) { //第一个元素就不用比较了，直接看第二个元素能不能插进去，i：每次要插入的元素的下标
int j = i - 1;
int tmp = array[i];
for (; j >= 0 ; j--) {
if(array[j] > tmp){ //加等号就不稳定了
array[j + 1] = array[j];//你往前移动，让tmp插进去
}else{
break;
}
}
array[j +1] = tmp;//一个是循环里刚好(array[i] < tmp):array[j+1] = tmp;
}
}
直接插入排序的特性总结：1. 元素集合越接近有序，直接插入排序算法的时间效率越高2. 时间复杂度： O(N^2)3. 空间复杂度： O(1) ，它是一种稳定的排序算法4. 稳定性：稳定
二：希尔排序（缩小增量排序）
希尔排序法又称缩小增量法。（譬如一个8个元素的数组（先分成4组），我们第一次先让第一个元素和第五个元素比较，看看能不能插入，第二个和第六个元素比较，以此类推；第二次分成两组，第一个和第三个比较，然后第五个元素看看能不能插入第一个和第三个元素里面…………依次类推）
public static void shellSort(int[] array){
int gap = array.length;
while(gap > 1){
gap /= 2;
shell(array,gap);
}
}
public static void shell(int[] array, int gap){
for (int i = gap ; i < array.length; i++) {
int tmp = array[i];
int j = i - gap;
for (; j >= 0 ; j-= gap) {
if(array[j] > tmp){
array[j + gap] = array[j];
}else{
break;
}
}
array[j +gap] = tmp;
}
}
关于希尔排序的时间复杂度：一般认为是
并且是不稳定的
三： 选择排序（1）
3.1： 选择排序（1）
基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，,第二次从第二个位置开始~直到全部待排序的数据元素排完 。
/**
* 时间复杂度：O(n^2）（不管怎么样都是）(n-1)+……+2+1
* 空间复杂度：O(1)
* 稳定性：不稳定
* 堆排序
* @param array
*/
public static void chanceSort(int[] array){
//{ 9,3,5,6,2,4}
//首先就是第一个数字和后面的所有数字进行比较，找到一个最小的数字放在最前面
//譬如第一遍首先最小的是9，然后变成3，最后变成了2的下标
//第二次从第二个元素开始往后找、找最小的元素
for (int i = 0; i < array.length; i++) {
int minIndex = i;
for (int j = i +1; j < array.length; j++) {
if(array[j] < array[minIndex]){
minIndex = j;
}
}
swap(array , minIndex,i);
}
}【 直接选择排序的特性总结 】1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用2. 时间复杂度： O(N^2)（不管怎么样都是O(n)）3. 空间复杂度： O(1)4. 稳定性：不稳定
3.2： 选择排序（2）
public static void chanceSort2(int[] array){
//我的评价是不如上面那个方法，因为你俩的的时间复杂度完全一样
//{ 9,3,5,6,2,4}
int left = 0;
int right = array.length-1;
while(left < right){ //你俩相遇了就不用比了
int maxIndex = left;
int minIndex = left;
//这个i = left +1(从第二个元素和第一个元素进行比较）
for (int i = left + 1; i <= right;i++) {//right = array.length
if(array[i] < array[minIndex]){
minIndex = i;
}
//找到最大的元素放在最后
if(array[i] > array[maxIndex]){
maxIndex = i;
}
}
swap(array , minIndex,left);
//最大值刚好在最小值的位置，所以说最大值已经被交换到了“现在的minIndex的位置”
if(maxIndex == left){
maxIndex = minIndex;
}
swap(array,maxIndex,right);
left++;
right--;
}
}
四：堆排序(Heapsort)
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆 来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
public static void heapSort(int[] array){
createBigHeap(array);//创建一个大根堆
int end = array.length -1;
//为什么要一开始end = array.length-1呢因为，我向下调整的时候不需要调整最后一个元素（最大的一个元素）
while(end != 0) {
swap(array, 0, end);//交换是肯定要交换最后一个元素啦
shiftDown(0, array,end);//这里传的是array.length -1(不需要调整最后那个大的元素）
end --;
}
}
public static void createBigHeap(int []array){
for (int parent = (array.length-1 -1)/2; parent >= 0; parent--) {
shiftDown(parent,array,array.length);//这里减一
}
}
private static void shiftDown(int parent, int []array,int end) {
int child = parent *2 +1;
while(child < end){ //我创建大根堆的时候传过来的end =array.length
//但是我堆排序的时候每次不需要调整最后一个元素了，所以传过来的是array.length-1
if(child +1 < end && array[child] < array[child +1]){ //更改
child++;
}
if(array[child] > array[parent]){
swap(array,parent,child);
parent = child;
child = parent *2 +1;
}else{
break;
}
}
}【 直接选择排序的特性总结 】
1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度： O(N*logN)
3. 空间复杂度： O(1)
4. 稳定性：不稳定
五：交换排序
/**
* 2. 时间复杂度：O(N^2),经过改良之后最小为O(n)(完全有序，走一遍就break了）
* 3. 空间复杂度：O(1)
* 4. 稳定性：稳定
* @param array
*/
public static void bubbleSort(int[] array){
for (int i = 0; i < array.length; i++) {
boolean flag = false;
for (int j = 0; j < array.length -1 -i; j++) {
if(array[j] > array[j+1]){
swap(array,j,j+1);
flag = true;
}
}
if(flag == false){
break;
}
}
}六：快速排序
快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法，其基本思想为： 任取待排序元素序列中的某元 素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有 元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止 。（递归）
public static void quickSort(int[] array){
quick(array,0,array.length -1);
}
public static void quick(int[] array,int start,int end) {
if(start >= end){
return;
}
int pivot = quickSortSmall(array,start,end);
quick(array,start,pivot- 1);//这里一定要注意开始的边界一定要是start,不能是0
//你要想想如果，现在正在递归我右边的左边（这个起始其实应该是pivot+1）
quick(array,pivot +1,end);
}
public static int quickSortSmall(int[] array, int left, int right){
int location = left;//保留我原来的最左边的下标
int key = array[left];
while(left < right){
while(left < right && array[right] >= key){ //大循环里面的小循环一定要注意边界
right--;
}
while(left < right && array[left] <= key){//都要加等号，不然可能走不动呀
left++;
}
swap(array,left,right);
}
swap(array , location,left);让相遇点下标的值和我的起始值进行交换
//每次相遇的时候的值都小于等于我的起始值，
//情况一：right动到left(由于right先动的，left还处于上一次交换完的<key
//情况二：left动到了right，想都不用想，right先动到了小于key的值
//情况三：一开始left就没动过，right一下就到了left（相当于这个树没有左子树）
return left;
}Test：测试七大排序算法
（冒泡除外）
import java.util.Arrays;
import java.util.Random;
public class Test {
public static void orderArray(int[] array){
for (int i = 0; i < array.length; i++) {
array[i] = i;
}
}
public static void notOrderArray(int[] array){
for (int i = 0; i < array.length; i++) {
array[i] = array.length - i;
}
}
public static void randomArray(int[] array){
Random random = new Random();
for (int i = 0; i < array.length; i++) {
array[i] = random.nextInt(100000);
}
}
public static void testInsertSort(int[] array){
//这样不对 ：int []tmpArray = array;
//要copy，不然你给我排序了，后面的就是有序了呀
int[] tmpArray = Arrays.copyOf(array,array.length);
//开始和结束的时间
long startTime = System.currentTimeMillis();
Sort.insertSort(tmpArray);
long endTime = System.currentTimeMillis();
//这里一定要加括号呀，不然就相当于你一个字符串减去一个数字，肯定报错
System.out.println("插序消耗时间:" + (endTime - startTime));
}
public static void main2(String[] args) {
int[] array = new int[10000];
//orderArray(array);
notOrderArray(array);
//randomArray(array);
testInsertSort(array);
testShellSort(array);
testQuickSort(array);
testHeapSort(array);
}
public static void main(String[] args) {
//int[] array = new int[100000];
int []array = {4,5,3,8,2};
Sort.bubbleSort(array);
//Sort.shellSort(array);
//Sort.chanceSort2(array);
//Sort.heapSort(array);
//Sort.quickSort(array);
System.out.println(Arrays.toString(array));
}
}上述就是排序算法漫游：从冒泡到堆排的底层逻辑与性能厮杀
的全部内容了，能看到这里相信您一定对小编的文章有了一定的认可。
有什么问题欢迎各位大佬指出
欢迎各位大佬评论区留言修正~~