数组和链表

《图解算法》学习笔记之选择排序

数组和链表哪个用得更多呢？显然要看情况。但数组用得很多，因为它支持随机访问。有两
种访问方式：随机访问和顺序访问。顺序访问意味着从第一个元素开始逐个地读取元素。链表只
能顺序访问：要读取链表的第十个元素，得先读取前九个元素，并沿链接找到第十个元素。随机
访问意味着可直接跳到第十个元素。本书经常说数组的读取速度更快，这是因为它们支持随机访
问。很多情况都要求能够随机访问，因此数组用得很多。

选择排序

《图解算法》学习笔记之选择排序

需要检查的元素数越来越少

随着排序的进行，每次需要检查的元素数在逐渐减少，最后一次需要检查的元素都只有一
个。既然如此，运行时间怎么还是O(n2)呢？这个问题问得好，这与大O表示法中的常数相关。
第4章将详细解释，这里只简单地说一说。
你说得没错，并非每次都需要检查n个元素。第一次需要检查n个元素，但随后检查的元素
数依次为n  1, n – 2, …, 2和1。平均每次检查的元素数为1/2 × n，因此运行时间为O(n × 1/2 × n)。
但大O表示法省略诸如1/2这样的常数（有关这方面的完整讨论，请参阅第4章），因此简单地写
作O(n × n)或O(n2)。

小结

 计算机内存犹如一大堆抽屉。
 需要存储多个元素时，可使用数组或链表。
 数组的元素都在一起。
 链表的元素是分开的，其中每个元素都存储了下一个元素的地址。
 数组的读取速度很快。
 链表的插入和删除速度很快。
 在同一个数组中，所有元素的类型都必须相同（都为int、 double等）。

示例代码

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++11

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

C#

using System;
using System.Collections.Generic;

namespace ConsoleApplication
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var arr = new List<int> { 5, 3, 6, 2, 10 };
            Console.WriteLine(string.Join(", ", SelectionSort(arr)));
        }

        private static int[] SelectionSort(List<int> arr)
        {
            var newArr = new int[arr.Count];
            for (int i = 0; i < newArr.Length; i++)
            {
                var smallest = FindSmallest(arr);
                newArr[i] = arr[smallest];
                arr.RemoveAt(smallest);
            }
            return newArr;
        }

        private static int FindSmallest(List<int> arr)
        {
            var smallest = arr[0];
            var smallestIndex = 0;
            for (int i = 0; i < arr.Count; i++)
            {
                if (arr[i] < smallest)
                {
                    smallest = arr[i];
                    smallestIndex = i;
                }
            }
            return smallestIndex;
        }
    }
}

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]))

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
    private static int[] selectionSort(int[] arr) {
        int[] newArr = new int[arr.length];

        for (int i = 0; i < newArr.length; i++) {
            int smallestIndex = findSmallest(arr);
            newArr[i] = arr[smallestIndex];

            arr = getNewArrWithoutSmallest(arr, smallestIndex);
        }

        return newArr;
    }

    private static int[] getNewArrWithoutSmallest(int[] arr, int smallestIndex) {
        int[] newArrWithoutSmallest = new int[arr.length - 1];
        for (int i = 0; i < arr.length; i++) {
            if (i < smallestIndex) {
                newArrWithoutSmallest[i] = arr[i];
            } else if (i > smallestIndex) {
                newArrWithoutSmallest[i - 1] = arr[i];
            }
        }
        return newArrWithoutSmallest;
    }

    private static int findSmallest(int[] arr) {
        int smallest = arr[0];
        int smallestIndex = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < smallest) {
                smallest = arr[i];
                smallestIndex = i;
            }
        }
        return smallestIndex;
    }

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

JS

'use strict';
// Selection Sort - O(n^2)
// Parameter:
//  1. random array

// 1. Finds the smallest value in an array
function findSmallestIndex(array) {
  var smallestElement = array[0]; // Stores the smallest value
  var smallestIndex = 0; // Stores the index of the smallest value

  for (var i = 1; i < array.length; i++) {
    if (array[i] < smallestElement) {
      smallestElement = array[i];
      smallestIndex = i;
    }
  }

  return smallestIndex;
}

// 2. Sort the array
function selectionSort(array) {
  var sortedArray = [];
  var length = array.length;

  for (var i = 0; i < length; i++) {
    // Finds the smallest element in the array 
    var smallestIndex = findSmallestIndex(array);
    // Adds the smallest element to new array
    sortedArray.push(array.splice(smallestIndex, 1)[0]);
  }

  return sortedArray;
}

console.log(selectionSort([5, 3, 6, 2, 10])); // [2, 3, 5, 6, 10]

/**
 * Finds smallest element of an aray
 * @param {Array} arr array for searching
 * @return {number} index of the smallest element in array
 */
const findSmallest = ( arr ) => {
    let smallest = arr[0];
    let smallestIndex = 0;
    let arrLen = arr.length;

    for ( let i = 0; i < arrLen; i++ ) {
        if ( arr[i] < smallest ) {
            smallest = arr[i];
            smallestIndex = i;
        }
    }
    return smallestIndex;
};

/**
 * Sorts0 recursively an array of numbers
 * @param {Array} arr An array of numbers
 * @return {Array} New sorted array
 */
const selectionSort = ( arr ) => {
    if ( !arr.length ) return [];
    let smallest = arr.splice( findSmallest( arr ), 1 );
    return smallest.concat( selectionSort( arr ) );
};

let arr = [5, 3, 6, 2, 10];

console.log( selectionSort(arr) );

《图解算法》学习笔记之选择排序

数组和链表

选择排序

需要检查的元素数越来越少

小结

示例代码

C

C++11

C#

Python

JAVA

JS

相关推荐