前言：在了解各种排序算法之前，首先需要了解什么是时间复杂度、什么是空间复杂度、什么是常数时间操作。
表达式：
?
总结： （n+1）*（n/2）*2 +n
以下三种排序都是O(n^2)，但是最后一个插入排序性能更好，可能会为O(n):
1.选择排序
?
方法1：
package lqz;
/**
* Created by liu on 2021/7/20.
*/
public class SelectSort {
public static void main(String[] args) {
Integer[] integers = {1, 5, 8, 9, 2, 3, 4, 6};
getIntegerSort(integers);
for (int m =0 ;m< integers.length;m++){
System.out.println(integers[m]);
}
}
public static void getIntegerSort(Integer[] integers){
if(integers == null || integers.length<2){
return;
}
Integer num;
//0 --- N-1
//1 --- N-1
//.....
//N-2 --- N-1
for (int i = 0;i<integers.length-1;i++){
for (int j = i+1;j<integers.length;j++){
// integers[i] = integers[i] < integers[j] ? integers[i]: integers[j];
if(integers[i]> integers[j]){
num = integers[i];
integers[i] = integers[j];
integers[j] = num;
}
}
}
}
}方法2：
package lqz;
/**
* Created by liu on 2021/7/20.
*/
public class SelectSort2 {
public static void main(String[] args) {
Integer[] integers = {1, 5, 8, 9, 2, 3, 4, 6};
getIntegerSort(integers);
for (int m =0 ;m< integers.length;m++){
System.out.println(integers[m]);
}
}
public static void getIntegerSort(Integer[] integers){
if(integers == null || integers.length<2){
return;
}
Integer minNumIndex;
//0 --- N-1
//1 --- N-1
//.....
//N-2 --- N-1
for (int i = 0;i<integers.length-1;i++){
minNumIndex = i;
for (int j = i+1;j<integers.length;j++){
minNumIndex = integers[minNumIndex] <= integers[j] ? minNumIndex: j;
}
swapSort(integers,i,minNumIndex);
}
}
public static void swapSort(Integer[] integers,int i,int minNumIndex){
if(i != minNumIndex){
Integer middle = integers[i];
integers[i] = integers[minNumIndex];
integers[minNumIndex] = middle;
}
}
}
2.冒泡排序
package lqz;
/**
* Created by liu on 2021/7/20.
*/
public class BubbleSort {
public static void main(String[] args) {
Integer[] integers = {1, 5, 8, 9, 2, 3, 4, 6};
//0 --- N-1
//0 --- N-2
//...
//0 --- 1
for (int i = integers.length-1 ;i>0 ;i--){
// Integer maxMumIndex = i;
for (int m = 0;m < i;m++){
if(integers[m] > integers[m+1]){
int middle = integers[m];
integers[m] = integers[m+1];
integers[m+1] = middle;
}
}
}
for (int n=0 ;n< integers.length;n++){
System.out.println(integers[n]);
}
}
}
3.插入排序
就是打牌的例子：
方法一：
package lqz;
/**
* Created by liu on 2021/7/20.
*/
public class InsertSort {
public static void main(String[] args) {
Integer[] integers = {1, 5, 8, 9, 2, 3, 4, 6};
//0
//0- 1
//0- 2
//..
//0- N-1
for (int a= 1;a<integers.length;a++){
for (int m = a-1;m<a;m--){
if(integers[m] > integers[m+1]){
int middle = integers[m];
integers[m] = integers[m+1];
integers[m+1] = middle;
}else {
break;
}
}
}
for (int n=0 ;n< integers.length;n++){
System.out.println(integers[n]);
}
}
}
?
方法二：
package lqz;
/**
* Created by liu on 2021/7/20.
*/
public class InsertSort2 {
public static void main(String[] args) {
Integer[] integers = {1, 5, 8, 9, 2, 3, 4, 6};
//0- 1
//0- 2
//..
//0- N-1
for (int a= 1;a<integers.length;a++){
for (int m = a-1;integers[m] > integers[m+1] && m>=0;m--){
int middle = integers[m];
integers[m] = integers[m + 1];
integers[m + 1] = middle;
}
}
for (int n=0 ;n< integers.length;n++){
System.out.println(integers[n]);
}
}
}
?