排序算法之选择排序

排序算法中最优的时间复杂度级别为O(nlgn) 基础：O(n^2)，易于实现，因此在一些简单情境下可能是首选。

在一些特殊情况下，简单的排序算法更有效。简单的排序算法思想衍生出复杂的排序算法。可以作为子过程，用以改进更复杂的排序算法。

选择排序（Selection Sort）

1.选择排序的过程：

2.选择排序的算法实现

(1).c++代码：

#include <iostream> #include <algorithm> using namespace std; void SelectionSort(int arr[], int n);//c++中要先声明 int main(){ int data[9] = {1,2,4,7,8,3,5,99,52}; SelectionSort(data,9); for(int i = 0; i < sizeof(data); i++) cout << data[i]<<" "; cout<<endl; return 0; } void SelectionSort(int arr[], int n){ for(int i = 0; i < n; i++){ int minIndex = i; for(int j = i+1; j < n; j++){ if(arr[j] < arr[minIndex]) minIndex = j; } swap(arr[i],arr[minIndex]);//c++ 11标准库中的内置函数，如果不是使用11标准，需要include algorithm } }

(2).java代码：

SelectionSort类

package cuc.miti.qcl.sort; import java.util.Collections; /* * 选择排序 */ public class SelectionSort { public void SelectSort(int[] array){ for(int i = 0; i < array.length; i++){ int minIndex = i; for(int j = i+1; j < array.length; j++){ if(array[j] < array[minIndex]) minIndex = j; } //Collections.swap(array,array[minIndex],array[i]); 这个方法要把数组改成list swap(array[minIndex],array[i]); } } public void swap(int a, int b){ int temp = a; a = b; b = temp; } }

Main类

package cuc.miti.qcl.main; import cuc.miti.qcl.sort.SelectionSort; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub /* * 选择排序 */ int[] data = new int[]{1,2,43,22,63,5,9}; SelectionSort ss = new SelectionSort(); ss.SelectSort(data); for(int i = 0; i < data.length; i++){ System.out.print(data[i]+" "); } System.out.println(); } }

这种写法并没有实现选择排序，原因在于自己定义的swap()方法并没有实现值的交换。之所以没有进行值的交换是因为”Java对普通类型的变量是不支持引用传递的。”因此swap方法结束后就失效了。

在c++中标准库中的swap()的具体实现如下：

void swap(int&a ,int&b) { int temp; temp = a; a = b; b = temp; }

那么我们在java中可以使用下面这种方法来进行交换：

public void swap3(int[] data, int a, int b){ int t = data[a]; data[a] = data[b]; data[b] = t; }