排序算法(一)
1.冒泡排序-Bubble Sort
1.算法原理
依次比较相邻的两个元素,若按照从小到大的顺序,则将相邻元素中较大的一个放在后面;然后对每一对相邻元素都做这种比较,序列的最后一个元素就是最大的数;
2.算法复杂度
时间复杂度:最优复杂度:O(n);最差复杂度:O(n2);平均复杂度:O(n2)
空间复杂度:O(1)
3.算法实现-Java
public int[] bubbleSort(int[] arr){for(int i = 0; i < arr.length - 1; i++){for(int j = 0; j < arr.length -1 - i; j ++){if(arr[j] > arr[j + 1]){int temp = arr[j];int arr[j] = arr[j + 1];int arr[j + 1] = temp;}}}return arr;
}
2.选择排序-Selection Sort
1.算法原理
先在需要排序的序列中找到最大(小)的一个元素,将其放到序列的起始位置;
然后在剩余队列中找到最大(小)的一个元素,将其放到已经排列好的序列的末尾;
以此类推
2.算法复杂度
时间复杂度:最优复杂度:O(n2);最差复杂度:O(n2);平均复杂度:O(n2)
空间复杂度:O(1)
3.算法实现-Java
public int[] selectionSort(int[] arr){for(int i = 0; i < arr.length-1; i++){int minIndex = i;for(int j = i + 1; j < arr.length; j ++){if(arr[j] < arr[minIndex]){minIndex = j;}}if(minIndex != i){int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}return arr;
}
3.插入排序-Insertion Sort
1.算法原理
假设第一个元素为已排好序的序列,未排序的元素从已排好序的序列中从后向前扫描,找到相应的位置插入进去(原本这个位置的元素向后挪一位),组成新的已排好序的序列;以此类推,直到所有元素排序完成
2.算法复杂度
时间复杂度:最优复杂度:O(n);最差复杂度:O(n2);平均复杂度:O(n2)
空间复杂度:O(1)
3.算法实现-Java
public int[] insertionSort(int[] arr){for(int i = 1; i < arr.length; i++){int preIndex = i - 1;int currentValue = arr[i];while(preIndex >= 0 && currentValue< arr[preIndex]){arr[preIndex + 1] = arr[preIndex];preIndex -= 1;}arr[preInde + 1] = currentValue;}return arr;
}