冒泡排序：

  1. 两两比较确定最大数，依次确定第二大，第三大数
  2. 稳定 时间复杂度O(n^2^)
1
2
3
4
5
6
7
8
9
10
11
12
13
void sort(int[] nums) {
    if(nums == null || nusm.size() < 2)
        return;
    for ( int i = 0; i < nums.size()-1; ++i) {
        for(int j = 0; j < nums.size()-i-1;++j) {
            if(nums[j] > nums[j + 1]) {
                int temp = nums[j+1];
                nums[j+1] = nums[j];
                nums[j] = temp;
            }
        }
    }
}

插入排序：

  1. 从后向前扫描，如果发现前边的比当前的大，则将前边元素后移，直到找到已排序元素中小于当前位置元素的数
  2. 稳定 时间复杂度O(n^2^)
1
2
3
4
5
6
7
8
9
10
11
12
13
void sort(int[] nums) {
    if(nums == null || nums.length < 2)
        return ;
    for (iny i = 0; i < nums.length - 1; i++) {
		iny curr = nums[i+1];
        int preIndex = i;
        while ( preIndex >= 0 && curr < nums[preIdnex]) {
            nums[preIndex + 1] = nums[preIndex];
            preIndex--;
        }
        nums[preIndex + 1] = curr;
    }
}

选择排序：

  1. 从最小元素开始，依次找第二小，第三小元素（与冒泡排序对称相反）
  2. 不稳定 时间复杂度O(n^2^)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void sort(int[] nums) {
	for (int i = 0; i < nums.length; i++) {
		int minIndex = i;
		for (int j = i + 1; j < nums.length; j++) {
			if (nums[j] < nums[minIndex]) {
				minIndex = j;
			}
		}
		if (minIndex != i) {
			int temp = nums[i];
			nums[minIndex] = temp;
			nums[i] = nums[minIndex];
		}
	}
}

快速排序：

分治思想

思路：

  1. 从数组中选一个数做为基准值，一般选第一个数，或者最后一个数。
  2. 采用双指针(头尾两端)遍历，从左往右找到比基准值大的第一个数，从右往左找到比基准值小的第一个数，交换两数位置，直到头尾指针相等或头指针大于尾指针，把基准值与头指针的数交换。这样一轮之后，左边的数就比基准值小，右边的数就比基准值大。
  3. 对左边的数列，重复上面1，2步骤。对右边重复1，2步骤。
  4. 左右两边数列递归结束后，排序完成。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void sort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        quickSort(nums, 0, nums.length - 1);
    }
void quickSort(int[] nums, int star, int end) {
        if (star > end) {
            return;
        }
        int i = star;
        int j = end;
        int key = nums[star];
        while (i < j) {
            while (i < j && nums[j] > key) {
                j--;
            }
            while (i < j && nums[i] <= key) {
                i++;
            }
            if (i < j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        nums[star] = nums[i];
        nums[i] = key;
        quickSort(nums, star, i - 1);
        quickSort(nums, i + 1, end);
    }
}
//10万个数的数组，耗时：50毫秒

快排，面试最喜欢问的排序算法。这是运用分治法的一种排序算法。

快速排序

  1. 从数组中选一个数做为基准值，一般选第一个数，或者最后一个数。
  2. 采用双指针(头尾两端)遍历，从左往右找到比基准值大的第一个数，从右往左找到比基准值小的第一个数，交换两数位置，直到头尾指针相等或头指针大于尾指针，把基准值与头指针的数交换。这样一轮之后，左边的数就比基准值小，右边的数就比基准值大。
  3. 对左边的数列，重复上面1，2步骤。对右边重复1，2步骤。
  4. 左右两边数列递归结束后，排序完成。
  5. 不稳定 O(nlogn)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 void quickSort(int[] nums, int star, int end) {
        if (star > end) {
            return;
        }
        int i = star;
        int j = end;
        int key = nums[star];
        while (i < j) {
            while (i < j && nums[j] > key) {
                j--;
            }
            while (i < j && nums[i] <= key) {
                i++;
            }
            if (i < j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        nums[star] = nums[i];
        nums[i] = key;
        quickSort(nums, star, i - 1);
        quickSort(nums, i + 1, end);
    }
}
//10万个数的数组，耗时：50毫秒