设计一个好的算法通常要考虑哪些要求

发布网友发布时间：2022-04-24 21:10

共6个回答

好二三四时间：2022-06-13 06:56

排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是选择排序算法：

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n?) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

1. 算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

2. 动图演示

代码实现

JavaScript 代码实现

实例

Python 代码实现

实例

def selectionSort(arr):
for i in range(len(arr) - 1):
# 记录最小数的索引
minIndex = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[minIndex]:
minIndex = j
# i 不是最小数时，将 i 和最小数进行交换
if i != minIndex:
arr[i], arr[minIndex] = arr[minIndex], arr[i]
return arr

Go 代码实现

实例

func selectionSort(arr []int) []int {
length := len(arr)
for i := 0; i < length-1; i++ {
min := i
for j := i + 1; j < length; j++ {
if arr[min] > arr[j] {
min = j
}
}
arr[i], arr[min] = arr[min], arr[i]
}
return arr
}

Java 代码实现

实例

public class SelectionSort implements IArraySort {

@Override
public int[] sort(int[] sourceArray) throws Exception {
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

// 总共要经过 N-1 轮比较
for (int i = 0; i < arr.length - 1; i++) {
int min = i;

// 每轮需要比较的次数 N-i
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
// 记录目前能找到的最小值元素的下标
min = j;
}
}

// 将找到的最小值和i位置所在的值进行交换
if (i != min) {
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}

}
return arr;
}
}

PHP 代码实现

实例

C 语言

实例

void swap(int *a,int *b) //交換兩個變數
{
int temp = *a;
*a = *b;
*b = temp;
}
void selection_sort(int arr[], int len)
{
int i,j;

for (i = 0 ; i < len - 1 ; i++)
{
int min = i;
for (j = i + 1; j < len; j++) //走訪未排序的元素
if (arr[j] < arr[min]) //找到目前最小值
min = j; //紀錄最小值
swap(&arr[min], &arr[i]); //做交換
}
}

C++

实例

template<typename T> //整數或浮點數皆可使用，若要使用物件（class）時必須設定大於（>）的運算子功能
void selection_sort(std::vector<T>& arr) {
for (int i = 0; i < arr.size() - 1; i++) {
int min = i;
for (int j = i + 1; j < arr.size(); j++)
if (arr[j] < arr[min])
min = j;
std::swap(arr[i], arr[min]);
}
}

C#

实例

static void selection_sort<T>(T[] arr) where T : System.IComparable<T>{//整數或浮點數皆可使用
int i, j, min, len = arr.Length;
T temp;
for (i = 0; i < len - 1; i++) {
min = i;
for (j = i + 1; j < len; j++)
if (arr[min].CompareTo(arr[j]) > 0)
min = j;
temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}

Swift

实例

import Foundation
/// 选择排序
///
/// - Parameter list: 需要排序的数组
func selectionSort(_ list: inout [Int]) -> Void {
for j in 0..<list.count - 1 {
var minIndex = j
for i in j..<list.count {
if list[minIndex] > list[i] {
minIndex = i
}
}
list.swapAt(j, minIndex)
}
}

原文地址：https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/2.selectionSort.md
参考地址：https://zh.wikipedia.org/wiki/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F

以下是热心网友对选择排序算法的补充，仅供参考：

热心网友提供的补充1：

Kotlin 实现

class SelectionSort { 
    /** 
    * 拓展IntArray为他提供数据两个数交换位置的方法 
    * @param i 第一个数的下标 
    * @param j 第二个数的下标 
    */ 
    fun IntArray.swap(i:Int,j:Int){ 
        var temp=this[i] 
        this[i]=this[j] 
        this[j]=temp 
    } 
    fun selectionSort(array: IntArray):IntArray{
        for (i in array.indices){ 
            //假设最小值是i 
            var min=i 
            var j=i+1 
            while (j in array.indices){ 
                if (array[j]<array[min]){ 
                    min=j
                }
                j++ 
            } 
            if (i!=min){
                array.swap(i,min) 
            } 
        } 
        return array; 
    }
}

以上为选择排序算法详细介绍，插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等排序算法各有优缺点，用一张图概括：

关于时间复杂度

平方阶 (O(n2)) 排序各类简单排序：直接插入、直接选择和冒泡排序。

线性对数阶 (O(nlog2n)) 排序快速排序、堆排序和归并排序；

O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。希尔排序

线性阶 (O(n)) 排序基数排序，此外还有桶、箱排序。

关于稳定性

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

名词解释：

n：数据规模

k："桶"的个数

In-place：占用常数内存，不占用额外内存

Out-place：占用额外内存

稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同

热心网友时间：2022-06-13 04:04

数据结构中评价一个好的算法，应该从四个方面来考虑，分别是：

一、算法的正确性。

二、算法的易读性。

三、是算法的健壮性。

四、是算法的时空效率（运行）。

算法的设计取决于数据（逻辑）结构，算法的实现取决于所采用的存储结构。数据的存储结构本质上是其逻辑结构在计算机存储器中的实现。为了全面反映一个数据的逻辑结构，它在内存中的影像包括两个方面，即数据元素之间的信息和数据元素之间的关系。

不同的数据结构有相应的操作。数据的操作是在数据的逻辑结构上定义的操作算法，如检索、插入、删除、更新和排序。

扩展资料

该算法的一般性质包括：

1．通用性对于任何符合输入类型的输入数据，都可以根据算法解决问题，并且包保证了计算结构的正确性。

2．算法的每一条指令都必须能够被人或机器执行。

3．确定性算法应该在每一步之后都有明确的下一步指示。也就是说，确保每个步骤都有下一步行动的指示，不缺少或只包含含糊的下一步行动指示。

4．有限算法的执行必须在有限步结束。

参考资料来源：百度百科-数据结构（计算机存储、组织数据方式）

热心网友时间：2022-06-13 05:22

数据结构中评价一个好的算法，应该从四个个方面来考虑，分别是：

一、算法的正确性。

二、算法的易读性。

三、是算法的健壮性。

四、是算法的时空效率（运行）。

算法的设计取决于数据（逻辑）结构，算法的实现取决于所采用的存储结构。数据的存储结构本质上是其逻辑结构在计算机存储器中的实现。为了全面反映一个数据的逻辑结构，它在内存中的映像包括两个方面，即数据元素之间的信息和数据元素之间的关系。

不同的数据结构有相应的操作。数据的操作是在数据的逻辑结构上定义的操作算法，如检索、插入、删除、更新和排序。

扩展资料

算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法，厄米变形模型，随机森林算法。

算法可以宏泛的分为三类：

一、有限的，确定性算法这类算法在有限的一段时间内终止。他们可能要花很长时间来执行指定的任务，但仍将在一定的时间内终止。这类算法得出的结果常取决于输入值。

二、有限的，非确定算法这类算法在有限的时间内终止。然而，对于一个（或一些）给定的数值，算法的结果并不是唯一的或确定的。

三、无限的算法是那些由于没有定义终止定义条件，或定义的条件无法由输入的数据满足而不终止运行的算法。通常，无限算法的产生是由于未能确定的定义终止条件。

热心网友时间：2022-06-13 06:56

数据结构中评价一个好的算法，应该从四个个方面来考虑，分别是：

一、算法的正确性。

二、算法的易读性。

三、是算法的健壮性。

四、是算法的时空效率（运行）。

不同的数据结构有相应的操作。数据的操作是在数据的逻辑结构上定义的操作算法，如检索、插入、删除、更新和排序。

扩展资料：

算法的一般性质包括：

1、通用性对于那些符合输入类型的任意输入数据，都能根据算法进行问题求解，包保证计算结构的正确性。

2、有效性组成算法的每一条指令都必须是能够被人或机器确切执行的。

3、确定性算法每执行一步之后，对于它的下一步，应该有明确的指示。即，保证每一步之后都有关于下一步动作的指令，不能缺乏下一步指令或仅仅含有模糊不清的指令。

4、有穷性算法的执行必须在有限步内结束。

参考资料来源：百度百科-数据结构（计算机存储、组织数据方式）

热心网友时间：2022-06-13 08:48

实现简单，计算机的处理速度快！我以前看到一句话是说：能自己解决的问题不要去交给计算机处理，计算机是帮助用户解决问题的。能实现这些应该就差不多了！

热心网友时间：2022-06-13 10:56

时间复杂度、空间复杂度、需求。