<article class=“article fmt article-content”><h2>抉择排序</h2><h4>目录</h4><ul><li>1.算法思维</li><li>2.从[算法思维]到[代码实现]</li><li>3.代码实现(C、Python)</li></ul><h3>1. 算法思维</h3><blockquote>抉择排序:每一轮抉择出 <code>以后未排序区间中最小的元素</code>放到 <code>对应的地位</code>上</blockquote><p>排序过程:</p><p>数组a有n个元素</p><ul><li>第一轮:a[0]-a[n-1]为待排序区间,在此区间中选出最小的元素放在a[0]上;</li><li>第二轮:a[1]-a[n-1]是新的待排序区间,在此区间中选出最小的元素放到a[1]上;</li><li><p>第三轮:a[2]-a[n-1]是新的待排序区间,在此区间中选出最小的元素放到a[2]上;</p><p>….</p></li><li>第 n-1 轮:通过下面的排序,从a[0]-a[n-2]顺次放入了最小、次小..的元素,a[0]-a[n-2]为有序区间,此时待排序区间只剩下一个元素即最初一个元素,无需再进行排序,整个数组排序结束。</li></ul><h3>2.从“算法思维”到“代码实现”</h3><p>察看上述算法中的排序过程</p><ol><li>共须要n-1轮排序,每一轮排序外部的操作都一样,因而能够用for循环来实现每一轮排序。循环变量 i 的取值范畴为[0,n-1]</li><li>在每一轮排序外部为了最终找出剩下区间中最小的元素,须要遍历整个剩下的区间。因而每一轮排序外部也有一个for循环。循环变量 j 的取值范畴为[i+1,n-1]</li></ol><p>综上所述,算法能够应用2层for循环来实现</p><ul><li>外层的循环次数是排序轮次,有n个元素,则循环n-1次;这个for循环实现每一轮排序</li><li><p>内层for循环实现在每一轮排序外部找出剩下区间中的最小元素</p><p>双层for循环示意图:<br/><br/></p></li></ul><h3>3. 代码实现(C、Python)</h3><p>C语言实现</p><pre><code>//替换2个变量的值void Swap(int *a,int *b){ int temp = *a; *a =*b; *b = temp;}//抉择排序void SelectionSort(int *arr, int n) { //从数组起始地位开始,i初始化为0; for (int i = 0; i < n - 1; i++) { // 假如以后地位为最小元素 int min_index = i; //遍历待排序区间[i+1 - n-1],如果存在更小的元素则更新min_index for (int j = i + 1; j < n; ++j) { if (arr[min_index] > arr[j]) { //循环查找最小值 min_index = j; } } //查看min_index是否被更新过,是则将最小元素替换到地位i if(min_index!=i) { //应用替换,防止笼罩掉原先地位的元素 Swap(&arr[i], &arr[min_index]); } }}</code></pre><p>Python实现</p><pre><code>def SelectSort(arr): length = len(arr) for i in range(0,length-1): min_tmp=i for j in range(i+1,length): if arr[j]<arr[min_tmp]: min_tmp=j if min_tmp!=i: arr[i],arr[min_tmp] = arr[min_tmp],arr[i] </code></pre></article>