博客

选择排序

选择排序时间复杂度：



O

O(n^2)






O


(



n










2









)

直接上代码

Java:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SelectionSort {

    private static List<Integer> selectionSort(List<Integer> arr) {
        List<Integer> newArr = new ArrayList<>(arr.size());

        int size = arr.size();
        for (int i = 0; i < size; i++) {
            int smallest = findSmallest(arr);
            newArr.add(arr.get(smallest));

            arr.remove(smallest);
        }

        return newArr;
    }

    private static int findSmallest(List<Integer> arr) {
        int smallest = arr.get(0);
        int smallestIndex = 0;
        for (int i = 0; i < arr.size(); i++) {
            if (arr.get(i) < smallest) {
                smallest = arr.get(i);
                smallestIndex = i;
            }
        }
        return smallestIndex;
    }

    public static void main(String[] args) {
        List<Integer> arr = new ArrayList<>(Arrays.asList(5, 3, 6, 2, 10));
        System.out.println(selectionSort(arr)); //[2, 3, 5, 6, 10]
    }
}

import java.util.Arrays;

public class SelectionSort2 {

    // this version uses raw arrays instead of ArrayList
    public static void selectionSort(int[] target) {
        for (int i = 0; i < target.length - 1; i++) {
            int left = target[i];
            for (int j = i + 1; j < target.length; j++) {
                int right = target[j];
                if (left > right) {
                    target[i] = right;
                    target[j] = left;
                    left = right;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 6, 2, 10};
        selectionSort(arr);
        System.out.println(Arrays.toString(arr)); // [2, 3, 5, 6, 10]
    }
}

C：

#include <stdio.h>
#include <stdlib.h>
#define SIZE 5

// Finds the smallest value in an array
int findSmallest(int *arr) {
	// Stores the smallest value
	int smallest = arr[0];
	// Stores the index of the smallest value
	int smallest_index = 0;
	for (int i = 1; i < SIZE; i++) {
		if (arr[i] < smallest) {
			smallest = arr[i];
			smallest_index = i;
		}
	}
	return smallest_index;
}

int *selectionSort(int *arr) {
	// Create new Array
	int *newArr = (int *)malloc(SIZE * sizeof(int));
	for (int i = 0; i < SIZE; i++) {
		int smallest = findSmallest(arr);
		newArr[i] = arr[smallest];
		// same as deleted by changing to the largest value
		arr[smallest] = INT_MAX;
	}
	return newArr;
}

int main(void) {
	int arr[SIZE] = {5, 3, 6, 2, 10};
	int *sortarr = selectionSort(arr);
	// print result
	for (int i = 0; i < SIZE; i++) {
		printf("%d ", sortarr[i]);
	}
	return 0;
}

C++：

#include <iostream>
#include <vector>

using std::cout;
using std::endl;

// Finds the smallest value in an array
template <typename T>
int find_smallest(const std::vector<T>& arr) {
    // stores smallest value
    T smallest = arr[0];
    // stores index of the smallest value
    int smallest_index = 0;

    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] < smallest) {
            smallest = arr[i];
            smallest_index = i;
        }
    }

    return smallest_index;
}

template <typename T>
std::vector<T> selection_sort(std::vector<T> arr) {
    std::vector<T> sorted;

    while(!arr.empty()) {
        // find smallest element and add it to sorted array
        int smallest_index = find_smallest(arr);
        sorted.push_back(arr[smallest_index]);

        // remove smallest element from non-sorted array
        arr.erase(arr.begin() + smallest_index);
    }

    return sorted;
}

int main() {
    std::vector<float> arr = {1.2, 1.0, 3, 0, -1, 0.5, 100, -99};
    std::vector<float> sorted = selection_sort(arr);
    
    cout << "Sorted array: ";
    for (float num : sorted) {
        cout << num << " ";
    }
    cout << endl;
}

Python：

# Finds the smallest value in an array
def findSmallest(arr):
  # Stores the smallest value
  smallest = arr[0]
  # Stores the index of the smallest value
  smallest_index = 0
  for i in range(1, len(arr)):
    if arr[i] < smallest:
      smallest_index = i
      smallest = arr[i]      
  return smallest_index

# Sort array
def selectionSort(arr):
  newArr = []
  for i in range(len(arr)):
      # Finds the smallest element in the array and adds it to the new array
      smallest = findSmallest(arr)
      newArr.append(arr.pop(smallest))
  return newArr

print(selectionSort([5, 3, 6, 2, 10]))