冒泡排序
排序思路：对于一个未排序的数组，我们两两对比数组元素，将较大的元素后移，这样经过一轮循环后，最大的元素就会移动至数组的最后端，然后再对除了最后一个元素的数组进行冒泡排序，直到数组有序为止。
时间复杂度：O（n2）
空间复杂度：O（1）
稳定性：稳定
public void bubbleSort(int[] nums){
int length = nums.length;
for (int i = length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j+1]){
swap(nums,j,j+1);
}
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
对冒泡排序可以进行改进，发现当某一次遍历时若无出现数组元素的两两交换，证明数组已经有序，可以退出循环。为此可以声明一个boolean类型的变量flag，记录是否发生数组元素的交换。
改进版代码如下：
public class BubbleSort {
public void bubbleSort(int[] nums){
int length = nums.length;
for (int i = length - 1; i > 0; i--) {
boolean flag = false;
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j+1]){
swap(nums,j,j+1);
flag = true;
}
}
if (!flag) break;
}
}
选择排序
排序思路：对于一个无序的数组，我们选取一个最大的元素，与数组最后一个元素进行交换，然后再对除了最后一个元素的数组继续进行选择排序，直到数组有序为止。
时间复杂度：O（n2）
空间复杂度：O（1）
稳定性：不稳定（涉及到不相邻元素的交换:例子1,6,3,7,3）
public void selectSort(int[] nums){
int length = nums.length;
for (int i = length - 1; i > 0; i--) {
int max = nums[0];
int index = 0;
for (int j = 0; j <= i; j++) {
if (max < nums[j]){
index = j;
max = nums[j];
}
}
swap(nums,index,i);
}
}
private void swap(int[] nums,int i,int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
快速排序
排序思路：对于一个无序的数组，我们选取一个基准元素，然后将小于等于基准元素的元素全部移动至基准元素左面，将大于等于基准元素的元素全部移动至数组右面，这样基准元素的位置就可以确定下来，然后分别再对基准元素左面和右面的部分进行快速排序。
时间复杂度：平均O（nlogn），最坏O（n2）
空间复杂度：平均O（logn），最坏O（n）（系统递归调用需要系统栈，基准元素选的好，能够将数组更平均分割，O（logn）；选不好，O（n））
稳定性：不稳定（涉及到不相邻元素的交换:例子1,6,3,7,3）
public void quickSort(int[] nums,int start,int end){
if (start < end){
int index = partition(nums,start,end);
quickSort(nums,start,index - 1);
quickSort(nums,index + 1,end);
}
}
private int partition(int[] nums, int start, int end) {
int left = start,right = end;
while(left < right){
while(left < right && nums[right] >= nums[start]) right--;
while(left <right && nums[left] <= nums[start]) left++;
swap(nums,left,right);
}
swap(nums,left,start);
return left;
}
private void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
对快速排序的改进：
- 采用三元素划分，选择三个数组元素，将中间值作为基准元素
- 随机选取基准元素，不选取首位
快速排序的优点：
- 平均时间复杂度低，是最常用的排序算法
- 由于每次访问的数组元素都是相近的，所以说快速排序可以利用到缓存技术，归并却不行
快速排序的缺点：
- 空间复杂度较高，对于元素较少时候可以不用快速排序，可以切换到插入排序。
归并排序
排序思路：对于一个数组，将这个数组一分为二，分别对左右两个数组进行归并排序，然后合并。证明归并排序是递归定义的。
时间复杂度：平均O（nlogn）
空间复杂度：平均O（logn），（与快速排序不同，归并排序每次都能保证平均分开数组，所以递归平均深度为logn）
稳定性：稳定
public void mergeSort(int[] nums,int start,int end){
if (start < end){
int mid = (start + end) / 2;
mergeSort(nums,start,mid);
mergeSort(nums,mid+1,end);
merge(nums,mid,start,end);
}
}
private void merge(int[] nums, int mid, int start, int end) {
int[] arr = new int[nums.length];
int left = start,right = mid + 1,count = 0;
while(left <= mid && right <= end){
if (nums[left] < nums[right]) {
arr[count++] = nums[left++];
}
else arr[count++] = nums[right++];
}
while(left <= mid){
arr[count++] = nums[left++];
}
while(right <= end){
arr[count++] = nums[right++];
}
for (int i = 0; i < count; i++) {
nums[i+start] = arr[i];
}
}
归并排序的优点：
- 时间复杂度低
归并排序的缺点：
- 不能利用缓存技术
- 空间复杂度高
计数排序
计数排序是指当待排序数组target中元素范围已知的情况下，可以对数组中的元素进行计数,，。
- 声明一个辅助数组arr，长度C为target中最大值-最小值+1，arr用来记录target数组中各元素的出现次数，；
- 计数，遍历待排序数组target，记当前元素为i，令arr[i] ++，即arr数组中下标为i的元素增加1;
- 对arr进行遍历，arr[i]的值i为arr[i]出现的次数,顺序输出即为target排好序的结果
时间复杂度：O（N+C）C为target数组中最大值-最小值+1，target的长度（arr的总和）为N
空间复杂度：O（C）或O（N）
计数排序的特点：
牺牲空间换取时间，但是如果O（N+C） > O(NlogN)，不如使用快排，还是看C的具体情况。
|