Clever Geek Handbook

选择排序

你好。我写这篇文章是专门为OTUS 开设“算法和数据结构”课程而设计的。







介绍



排序数组是计算机科学专业经典课程“算法和数据结构”中研究的第一个严重问题之一。在这方面，作为实习生或初级开发人员，在面试中经常会遇到写作任务和相应的问题。



问题的提法



传统上，值得用其陈述开始介绍问题的解决方案。通常，排序任务涉及按升序对一些整数数组进行排序。但是实际上，这有点过分简单了。本节中描述的算法可用于对在其之间建立排序关系的任何对象的数组进行排序（即对于任何两个元素，我们可以说：第一个大于第二个，第二个大于第一个，或者它们相等）。您可以按升序和降序排序。我们将使用标准简化。



选择排序



最简单的排序之一是选择排序。



算法说明



通过选择对数组进行排序的过程如下：将数组分为两部分。一部分称为已排序，另一部分称为未排序。该算法假定遍历整个数组，以使排序部分的长度等于整个数组的长度。在每次迭代中，我们在数组未排序部分中找到最小值，并将此最小值与数组未排序部分的第一个元素交换。然后，我们将数组排序部分的长度加一。下面给出了一个迭代的示例：

1 3 5 | 8 9 6-> 1 3 5 6 | 9 8



实作



我建议在C中查看此算法的实现： 



void choiseSortFunction(double A[], size_t N)
{
    for(size_t tmp_min_index = 0; tmp_min_index < N;
                                  tmp_min_index++) {
        // 
        for(size_t k = tmp_min_index + 1; k < N; k++) {
            if (A[k] < A[tmp_min_index]) {
                double min_value = A[k];
                A[k] = A[tmp_min_index];
                A[tmp_min_index] = min_value;
            }
        }
    }
}


分析



我建议分析此算法。内部循环的主体本身为O（1），即它不依赖于要排序的数组的大小。这意味着要了解算法的渐近性，有必要计算该主体的执行次数。在外循环的第一次迭代中，内循环有（n-1）次迭代。在外循环的第二次迭代中-（n-2）内循环的迭代。继续这种推理，我们得出以下结论：

T(n)=(n−1)∗O(1)+(n−2)∗O(1)+...+O(1)=O((n−1)+(n−2)+...+1)=O((n−1)∗n/2)=O(n2)





在计算过程中，我们首先使用O符号的属性，然后使用公式来计算算术级数的总和。



为了订购，还必须估计执行算法所需的额外内存。这里的一切都更加简单：我们仅为循环计数器和一个变量（一个缓冲区）分配了内存，该缓冲区允许交换2个数组元素。因此：

M(n)=O(1)





分析的结果是，得出的结论是算法的时间复杂度取决于输入数组的大小。因此，该排序属于二次排序的类。分析的结果不依赖于数组的内容：它在最佳，最差和平均水平上都是正确的。



同样重要的是要注意，选择排序在此实现中很可靠。让我提醒您，排序称为稳定。如果equal元素的顺序在其执行期间不发生变化。此属性对于诸如对数字数组进行排序这样的教育任务不是很重要，但是如果我们使用已建立的排序关系对一些更复杂的对象进行排序，则可能很重要。下一次我们谈论基数排序时，我们可以考虑一个类似的示例。



双面选择排序



上面实现的算法的优化可能会引起一些兴趣：在遍历数组的未排序部分时，可以并行搜索最大值和最小值元素。因此，在迭代之后，可以将数组的未排序部分减少1，而不是2。该算法没有渐近改进，但是执行速度可能会略有提高，比较次数也将增加一倍。



递归选择排序



作为练习，您可以尝试不使用循环而是使用递归来编写算法。在Java中，它可能看起来像这样： 



public static int findMin(int[] array, int index){
    int min = index - 1;
    if(index < array.length - 1) min = findMin(array, index + 1);
    if(array[index] < array[min]) min = index;
    return min;
}
  
public static void selectionSort(int[] array){
    selectionSort(array, 0);
}
  
public static void selectionSort(int[] array, int left){
    if (left < array.length - 1) {
        swap(array, left, findMin(array, left));
        selectionSort(array, left+1);
    }
}
  
public static void swap(int[] array, int index1, int index2) {
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
}


结果



我们研究了一种二次排序：选择排序，研究了使用循环的稳定实现，递归，并讨论了通过对数组未排序部分进行双向缩减来进行算法优化。排序纯粹是教育性的，在实践中尚未发现广泛的应用。





如果您想进一步了解该课程，我邀请所有人参加将于7月10日举行的免费网络研讨会。





More articles:


All Articles