C++和Java实现基本的选择排序和常见错误

C++和Java实现基本的选择排序和常见错误

一、选择排序的基本思想：

       首先，找到数组中最小的元素，其次将它和数组第一个元素交换位置（如果第一个元素就是最小元素则和自己交换），然后在剩下的元素中找到最小的元素，将它与数组第二个元素交换位置。如此循环，直到将整个数组排序。这种方法叫做选择排序。

       对于长度为N的数组，选择排序需要大约N^2/2次比较和N次交换

C++代码实现：

#include<iostream>

using namespace std;
template<typename T>
void selectionSort(T a[],int N) {
        for (int i = 0; i < N; i++) {
       
            int min = i;
            for (int j = i + 1; j < N; j++)
                if (a[min] > a[j])
                    min = j;
                    swap(a[i],a[min]);
        }
    }

int main() {
    int arr[10] = { 10,5,2,6,3,4,7,9,8,1 };
    selectionSort(arr,10);
    for (int i = 0; i < 10; i++)
        cout << arr[i] << " ";
    cout << endl;
    system("pause");

}

Java代码实现：

package selectionsort;

public class SelectionSort {
    public static void selectionSort(Comparable[] a){
        int N=a.length;
        for(int i=0;i<N;i++){
            int min=i;
            for(int j=i+1;j<N;j++)
                if(less(a[j],a[min]))
                    min=j;
                exch(a,i,min);
        }
    }
   
    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }
   
    private static void exch(Comparable[] a,int i,int j){
        Comparable t=a[i];a[i]=a[j];a[j]=t;
    }
   
   
   
    public static void main(String[] args) {
          Integer[] arr = {4,7,8,3,9,5,6,1,2}; 
          SelectionSort.selectionSort(arr);
          for( int i = 0 ; i <arr.length ; i ++ ){
              System.out.print(arr[i]);
              System.out.print(' ');
          }
       
    }
}

二、常见错误

问题描述：运行完程序后发现第一个元素与第二个元素没有排好序。如下图

解决：对于代码selectionSort方法中，if判断语句不要嵌套进第二个for循环中。

因为第二个for循环是为了寻找与i交换位置的元素，要循环找到后，才能判断它与i的大小关系。

本文永久更新链接地址：https://www.bkjia.com/Linux/2018-03/151412.htm