各种排序算法
1.Arrays.sort---默认升序
//降序排序
Integer a[] = {6,9,9};
Arrays.sort(a, Collections.reverseOrder());
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]);
}2.直接插入排序
① 从第一个元素开始，该元素可以认为已经被排序
② 取出下一个元素，在已经排序的元素序列中从后向前扫描
③如果该元素（已排序）大于新元素，将该元素移到下一位置
④ 重复步骤③，直到找到已排序的元素小于或者等于新元素的位置
⑤将新元素插入到该位置后
⑥ 重复步骤②~⑤
//降序排序
int temp = 0;
int a[] = {9,3,6,2,8,1,3} ;
if (a.length == 1){
System.out.println(a[0]);
} else {
for (int i = 1; i < a.length; i++) {
for (int j = 0; j < i ; j ++){
if (a[i] > a[j]){
temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}
}
}
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]);
}性能分析：
①平均时间复杂度：O(N^2)
②最差时间复杂度：O(N^2)
③空间复杂度：O(1)
④稳定性：稳定
3.希尔排序
将要排序的序列按照步长gap进行分组，先在这几组内进行插入排序，之后再进行整体的插入排序，gap步长的选择是希尔排序最重要的部分，要保证最后一次排序的步长为1，这样就会保证整个数组将会被排序，并且步长必须小于数组长度。
public void shellSort() {
//gap是为了分组；
int[] array = {9,3,6,2,8,1,3};
int gap = array.length;
while (gap > 1) {
//下一次的组数是上一次的一半；
gap /= 2;
shell(array, gap);
}
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]);
}
}
public void shell(int[] array, int gap) {
int temp = 0,b = gap;
for (int i = 0; i <= b; i++) {
if (array[gap] > array[i]){
temp = array[i];
array[i] = array[gap];
array[gap] = temp;
}
if (gap < array.length){
++gap;
}
}
}性能分析：
①最好情况：时间复杂度为O（n）
②最坏情况下：时间复杂度为O（n^2）
③空间复杂度为：O(1)
④稳定性：不稳定
4.选择排序
选择排序原理即是，遍历元素找到一个最小（或最大）的元素，把它放在第一个位置，然后再在剩余元素中找到最小（或最大）的元素，把它放在第二个位置，依次下去，完成排序。、
//降序排序
int temp = 0;
int a[] = {6,9,9} ;
for (int i = 0; i < a.length; i++) {
for (int j = i + 1; j < a.length ; j ++){
if (a[i] < a[j]){
temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}
}
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]);
}性能分析：
①时间复杂度：O（n^2）；
②空间复杂度：O（1）；
③稳定性：不稳定；
5.堆排序
-
从小到大排序建大堆，从大到小排序建小堆
-
把堆顶的元素和当前堆的最后一个元素交换
-
堆的元素个数减一
-
从根节点向下调整
性能分析：
①最好情况下时间复杂度为：O(nlogn)
②最坏情况下时间复杂度为：O(nlogn)
③空间复杂度为：O(1)
④稳定性：不稳定
6.冒泡排序
冒泡排序是一种简单的排序算法，它不断地重复遍历数组，每次与其相邻的数进行比较，如果他们的顺序错误就交换，直到数组只剩下一个元素的时候，说明该数组已经排好序，之所以成为冒泡排序，是因为越小的元素会经由交换慢慢“浮”到数列的前面。
//降序排序
int temp = 0;
int a[] = {8,3,9,4,5,2,6,8} ;
if (a.length == 1){
System.out.println(a[0]);
} else {
//每一趟都会排出一个最大/最小值，所以需要排序a.length - 1轮
for (int z = 0; z < a.length - 1; z++) {
int j = 1;
for (int i = 0; i < a.length -1;i++) {
if (a[i] < a[j]){
temp = a[j];
a[j] = a[i];
a[i] = temp;
}
j++;
}
}
}
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]);
}性能分析：
①最坏情况时间复杂度为：Ｏ（ｎ＾２）。
②平均情况时间复杂度为：Ｏ（ｎ＾２）。
③需要额外空间：Ｏ（１）。
④稳定性：稳定。
7.快速排序
这里是引用选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
性能分析：
①时间复杂度：最好情况：O（n*logn）；
最坏情况： O（n^2）；
②空间复杂度：最好情况：O（logn）；
最坏情况：O（n）；
③稳定性：不稳定；
引用：七大经典排序算法总结【详解】-CSDN博客