1.选择排序
每次把未排序的数组中的最小值放到当前位置。循环一定次数就达到了排序效果
public static void main(String[] args) {
int[] nums = {9, 5, 2, 7, 1};
for (int i = 0; i < nums.length - 1; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] > nums[j]) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
for (int n : nums
) {
System.out.print(n + " ");
}
System.out.println();
}
}一共五个数，找四次最小值即可排序：
第一次：1 9 5 7 2
第二次：1 2 9 7 5
第三次：1 2 5 9 7
第四次：1 2 5 7 9
- 时间复杂度：O(N2)
- 空间复杂度：O(1)
- 不稳定
2.冒泡排序
每次两两比较，如果大小位置不对，就交换，每趟会把最大的数交换到顶端，就像大的泡泡向上浮一样，故名其“冒泡”
public static void main(String[] args) {
int[] nums = {9, 5, 2, 7, 1};
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums.length - i - 1; j++) {
if (nums[j] > nums[j + 1]){
int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
for (int n : nums
) {
System.out.print(n + " ");
}
System.out.println();
}
}一组数： 9 5 2 7 1
我们看一下 9 上浮的过程：
5 9 2 7 1
5 2 9 7 1
5 2 7 9 1
5 2 7 1 9
就这样 9 到有序的位置了，然后在排序剩下的四个数即可，即内层循环的次数可以减 1 了；
关于冒泡的优化：为了明显地观察优化效果，我们数组变为 9 5 2 7 1 10
我们可以看一下，外层循环一共循环六次，分别如下：
第一次：5 2 7 1 9 10
第二次：2 5 1 7 9 10
第三次：2 1 5 7 9 10
第四次：1 2 5 7 9 10
第五次：1 2 5 7 9 10
第六次：1 2 5 7 9 10
我们可以看到，当到第四次的时候就已经有序了，完全不用进行第五次第六次循环，此时跳出循环即达到优化效果
我们可以添加一个判断条件，如果这次循环没有进行数据的交换（说明已经达到有序状态），跳出循环
public static void main(String[] args) {
int[] nums = {9, 5, 2, 7, 1, 10};
boolean f = false;
for (int i = 0; i < nums.length; i++) {
f = true;
for (int j = 0; j < nums.length - i - 1; j++) {
if (nums[j] > nums[j + 1]) {
f = false;
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
if (f){
break;
}
for (int n : nums
) {
System.out.print(n + " ");
}
System.out.println();
}
}
标志 f 用来判断跳出条件
- 时间复杂度：O(N2)
- 空间复杂度：O(1)
- 稳定
3.快速排序
快排的思想是用分割点把数组分成两个部分，分割点左边是比它小的数，右边是比它大的数，然后递归排序左边和右边的数，最终达到有序的目的。
public static void main(String[] args) {
int[] nums = {6, 2, 1, 5, 1, 1, 5, 6, 7, 8, 6, 4};
qsort(nums, 0, nums.length - 1);
for (int num : nums
) {
System.out.print(num + " ");
}
}
private static void qsort(int[] nums, int left, int right) {
if (left < right) {
int base = division(nums, left, right);
qsort(nums,left,base-1);
qsort(nums,base+1,right);
}
}
private static int division(int[] nums, int left, int right) {
int base = nums[left];
while (left < right) {
while (true) {
if (left > right) {
break;
}
if (nums[right] < base) {
nums[left] = nums[right];
break;
} else {
right--;
}
}
while (true) {
if (left >= right) {
break;
}
if (nums[left] >= base) {
nums[right] = nums[left];
break;
} else {
left++;
}
}
}
nums[left] = base;
return left;
}- 时间复杂度：O(Nlog2N)
- 空间复杂度：O(Nlog2N)
- 不稳定
4.插入排序
public class 插入 {
public static void main(String[] args) {
int[] nums = {9, 5, 2, 7, 1};
insertsqrt(nums);
}
private static void insertsqrt(int[] nums) {
for (int i = 1; i < nums.length; i++) {
int j = 0;
int temp = nums[i];
for (j = i - 1; j >= 0 && temp < nums[j]; j--) {
nums[j + 1] = nums[j];
}
nums[j + 1] = temp;
for (int n : nums
) {
System.out.print(n + " ");
}
System.out.println();
}
}
}一组数： 9 5 2 7 1
第一趟： 5 9 2 7 1
第二趟：2 5 9 7 1
第三趟：2 5 7 9 1
第四趟：1 2 5 7 9
- 时间复杂度：O(N2)
- 空间复杂度：O(1)
- 稳定
5.希尔排序
希尔排序就是 步长分组 + 插入排序
把步长分成多组，每组分别进行插入排序。
public class 希尔 {
public static void main(String[] args) {
int[] nums = {9,5,2,7,1};
shellsort(nums);
}
private static void shellsort(int[] nums) {
int N = nums.length / 2;
while (N != 0) {
for (int i = 1; i < nums.length; i++) {
int j = 0;
int temp = nums[i];
for (j = i - N; j >= 0 && temp < nums[j]; j -= N) {
nums[j + N] = nums[j];
}
nums[j + N] = temp;
}
for (int num : nums
) {
System.out.print(num + " ");
}
System.out.println();
N /= 2;
}
}
}
一组数： 9 5 2 7 1
把步长N分成 length / 2 ， 每次步长减半，最终到步长为1即为有序
length = 5
第一趟步长 N = 5/2=2；所以9 2 1 先排序，之后是 5 7排序
1 5 2 7 9
第二趟步长 N = N / 2 = 1;
1 2 5 7 9
此趟步长为1，完成就是有序的了
剩下还有堆排序、基数排序、桶排序、归并排序等等。