21xrx.com
2024-12-22 22:02:55 Sunday
登录
文章检索 我的文章 写文章
C++选择排序详解
2023-07-06 13:55:17 深夜i     --     --
C++ 选择排序 详解

选择排序是常用的一种排序算法,它的思路是每次从未排序的元素中选取最小的元素放到已排序部分的末尾。虽然它的时间复杂度为O(n^2),但它的代码实现较为简单,是入门学习排序算法的不错选择。在C++中实现选择排序也很容易,下面将进行详细的讲解。

首先需要明确的是,选择排序是一种不稳定排序算法。什么意思呢?假设数组中有两个相等的元素,它们的位置在未排序部分的中间,选择排序在每次选择最小元素时,可能会交换它们的位置,导致它们的顺序发生改变。因此,选择排序是不保证相同元素的相对位置的。

接下来,让我们通过一个例子来说明选择排序的具体实现。


void selectionSort(int arr[], int n){

  for (int i = 0; i < n-1; i++){

    int minIndex = i;

    for (int j = i+1; j < n; j++){

      if (arr[j] < arr[minIndex])

        minIndex = j;

       

    }

    swap(arr[i], arr[minIndex]);

  }

}

上述代码实现了一个从小到大排序的选择排序,其中arr是待排序的数组,n是数组中元素的个数。在这个算法中,每次在未排序部分中找到最小元素的下标,然后和未排序部分的开头位置进行交换,就完成了一次选择。

我们以 3为例,来模拟一下选择排序的过程。

首先,我们在未排序的部分中找到最小的元素1,将其与第一个元素4进行交换。此时,我们已经将最小的元素1放在了正确的位置,即已排序部分的末尾。

4

接下来,我们在未排序的部分中找到最小的元素2,将其与已排序部分的末尾进行交换。此时,前两个元素已经排好序了。

1

我们依次继续这样的操作,每次找到未排序部分中的最小元素,将其放到已排序部分的末尾。直至所有元素都排好序。

2

可以看到,选择排序的过程是一个不断缩小未排序部分的范围,同时将其中的最小元素放到已排序部分的末尾的过程。虽然它的时间复杂度相对较高,但它的思路具有一定的启示意义,例如可以用它来求解最小的k个元素。

综上所述,选择排序是一种简单易懂、时间复杂度为O(n^2)的不稳定排序算法。尽管它不适合处理大规模的数据,但作为入门学习排序算法的选择还是很不错的。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复