插入排序、冒泡排序、选择排序、快速排序、归并排序
以下所有排序都是实现升序
1.插入排序
【定义】
- 第一个元素自成一个有序数组A,从第二个元素开始,把每一个元素插入到有序数组A中合适的位置,满足有序的条件。直到最后元素,至此构建成一个有序数组。
【时间复杂度】
- O(n2)
【代码】
public void method(int [] array) {
int length = array.length;
int i,j;
for (i = 1; i < length; i++) {
int temp = array[i];
for (j = i-1; j >= 0 && array[j] > temp; j --) {
array[j+1] = array[j];
}
array[j+1] = temp;
}
}
补充:
在第二个for循环中,判断条件需要加上比较大小关系,
不能在for循环里面进行if判断,因为这样会导致最后一个元素的判断存在问题
2.冒泡排序
【定义】
- 从第一个元素开始,进行两两比较,如果前一个大于后一个,则进行交换,经过一轮交换之后,也就是一次冒泡,最大的元素就会在最后一个位置,在从第一个元素进行排序,两两比较,经过一轮交换之后,第二大的元素就在倒数第二个位置,以此类推
【时间复杂度】
- O(n2)
【代码】
public void method(int [] a) {
int i,j;
for (i = a.length; i > 0; i --) {
for (j = 0; j < i-1; j ++) {
if (a[j] > a[j+1]) {
int temp = a[j]</