数据结构&算法 选择排序

  • 选择排序

    选择排序是一种简单的排序算法。该排序算法是一种基于就地比较的算法,其中,列表分为两部分,左端为已排序部分,右端为未排序部分。最初,已排序部分为空,未排序部分为整个列表。从未排序的数组中选择最小的元素,并与最左边的元素交换,该元素成为排序数组的一部分。此过程继续将未排序的数组边界向右移动一个元素。该算法不适用于大型数据集,因为它的平均和最坏情况下的复杂度为Ο(n2),其中n是项数。
  • 选择排序如何工作?

    以下面描述的数组为例。
    selectsort
    对于排序列表中的第一个位置,将顺序扫描整个列表。当前存储14的第一个位置,我们搜索整个列表,发现10是最低值。
    selectsort
    因此,我们将10替换为14。一次迭代10(恰好是列表中的最小值)出现在已排序列表的第一位置。
    selectsort
    对于第二个位置(33个位置),我们开始以线性方式扫描列表的其余部分。
    selectsort
    我们发现14是列表中第二低的值,它应该出现在第二位。我们交换这些值。
    selectsort
    经过两次迭代后,两个最小值以排序的方式位于开头。
    selectsort
    将相同的过程应用于数组中的其余项目。
    以下是整个分类过程的图示-
    selectsort
    现在,让我们学习选择排序的一些编程方面。
  • 算法

    现在,我们对这种排序技术的工作原理有了更全面的了解,因此我们可以推导简单的步骤来实现选择排序。
    
    步骤 1 − 将最小值设置为位置0
    步骤 2 − 搜索列表中的最小元素
    步骤 3 − 在最小位置用值交换
    步骤 4 − 增加最小值以指向下一个元素
    步骤 5 − 重复,直到列表被排序
    
  • 伪码

    
    procedure selection sort 
       list  : array of items
       n     : size of list
    
       for i = 1 to n - 1
       /* set current element as minimum*/
          min = i    
      
          /* check the element to be minimum */
    
          for j = i+1 to n 
             if list[j] < list[min] then
                min = j;
             end if
          end for
    
          /* swap the minimum element with the current element*/
          if indexMin != i  then
             swap list[min] and list[i]
          end if
       end for
      
    end procedure
    
  • 实现

    以下是C语言的实现
    
    #include <stdio.h>
    #include <stdbool.h>
    
    #define MAX 7
    
    int intArray[MAX] = {4,6,3,2,1,9,7};
    
    void printline(int count) {
       int i;
      
       for(i = 0;i < count-1;i++) {
          printf("=");
       }
      
       printf("=\n");
    }
    
    void display() {
       int i;
       printf("[");
      
       // navigate through all items 
       for(i = 0;i < MAX;i++) {
          printf("%d ", intArray[i]);
       }
      
       printf("]\n");
    }
    
    void selectionSort() {
       int indexMin,i,j;
      
       // loop through all numbers 
       for(i = 0; i < MAX-1; i++) { 
      
          // set current element as minimum 
          indexMin = i;
        
          // check the element to be minimum 
          for(j = i+1;j < MAX;j++) {
             if(intArray[j] < intArray[indexMin]) {
                indexMin = j;
             }
          }
    
          if(indexMin != i) {
             printf("Items swapped: [ %d, %d ]\n" , intArray[i], intArray[indexMin]); 
          
             // swap the numbers 
             int temp = intArray[indexMin];
             intArray[indexMin] = intArray[i];
             intArray[i] = temp;
          }          
    
          printf("Iteration %d#:",(i+1));
          display();
       }
    }  
    
    void main() {
       printf("Input Array: ");
       display();
       printline(50);
       selectionSort();
       printf("Output Array: ");
       display();
       printline(50);
    }
    
    尝试一下