排序的思想就是维护一个有序的部分,将无序部分中最大的元素和最后一个元素相交换,交换后无序部分的最后一个元素也将有序。
通俗的讲,选择排序的原理就是:
先从头遍历一遍找出最大元素,最大元素和最后一个元素相交换。
再从头遍历到倒数第二个元素找出最大元素,最大元素和倒数第二个元素相交换。
直到所有元素都有序为止。
代码实现 /** * @Title: selectSort * @Description: 选择排序 * @param: array */public static void selectSort(int[] array) { int n = array.length; for (int i = 0; i < n; i++) { //记录最大元素的下标 int max = 0; for (int j = 0; j<n-i; j++) { if (array[j] > array[max]) { max = j; } } //最大元素和无序部分最后一个元素交换 if (max != n-1-i) { swap(array, max, n-1-i); } }}/** * @Title: swap * @Description: 交换数组array中下标为i和j的元素 * @param: array * @param: i * @param: j */private static void swap(int[] array, int i, int j) { array[i] = array[i] + array[j]; array[j] = array[i] - array[j]; array[i] = array[i] - array[j];} 时间复杂度和算法稳定性从代码中可以看出一共遍历了n + n-1 + n-2 + … + 2 + 1 = n * (n+1) / 2 = 0.5 * n ^ 2 + 0.5 * n,那么时间复杂度是O(N^2)。
因为在无序部分最大元素和有序部分第一个元素相等的时候,可以将无序部分最大元素放在前面,所以选择排序是稳定的。
相关代码都在github上:https://github.com/LebronChenX/sort喜欢这篇文章的朋友,欢迎长按下图关注公众号lebronchen,第一时间收到更新内容。