排序算法(一)

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;
}