选择排序(C++)算法(超详细)
发布时间:2020-12-16 07:38:03 所属栏目:百科 来源:网络整理
导读:冒泡排序在处理大型数组时的效率不够理想,因为经常需要重复的数据交换来将单个项目放置到正确的位置。 选择排序 和冒泡排序一样,每趟只放置一个项目到正确的位置。但是,通常情况下它执行的交换会比较少,因为它会立即将项目移动到数组中正确的位置。 像任
冒泡排序在处理大型数组时的效率不够理想,因为经常需要重复的数据交换来将单个项目放置到正确的位置。选择排序和冒泡排序一样,每趟只放置一个项目到正确的位置。但是,通常情况下它执行的交换会比较少,因为它会立即将项目移动到数组中正确的位置。 像任何其他排序一样,选择排序可以按照升序或降序的方式修改排序。按升序排序的方法如下:数组中最小的值被定位并移动到 Element 0,然后定位下一个最小值并移动到 Element 1,这个过程一直持续到所有元素都按照正确的顺序排列。 现在来看一看在排列下面数组的元素时,选择排序是如何工作的: 选择排序从 Element 0 开始扫描数组,并找到最小值的元素。这个元素的内容然后与 Element 0 的内容交换。在该示例中,Element 5 中存储的 1 是最小的值,所以它与存储在 Element 0 中的 5 交换。这完成了第一趟,现在的数组显示如下: 该算法然后重复该过程,但是因为 Element 0 已经包含数组中的最小值,所以可以将其排除在过程之外。接下来进行第二趟,算法在 Element 1 处开始扫描。它在数组的未排序部分中查找最小值,结果找到了 Element 2 中的 2。因此,Element 2 与 Element 1 交换。数组现在显示如下: 再次重复这个过程,但是这次扫描从 Element 2 开始。算法将发现 Element 5 包含下一个最小值,于是将该元素的内容与 Element 2 的内容交换,导致数组显示如下: ? ? 以下是选择排序算法的伪代码: For startScan = 0 to the next-to-last array subscript Set index to startScan Set minIndex to startScan Set minValue to array[startScan] For index = (startScan + 1) to the last subscript in the array If array[index] is less than minValue Set minValue to array[index] Set minIndex to index End If Increment index End For Set array[minIndex] to array[startScan] Set array[startScan] to minValue End For与冒泡排序一样,选择排序使用一对嵌套循环,在这个例子中是两个 for 循环。 外循环在每一趟排序时迭代一次。其循环控制变量是 startScan,它保存了数组元素的下标,该下标所代表的元素将在排序时接收其正确的值:
这个过程不断进行,直到从 Element 0 位置到倒数第 2 个位置的元素都已经获得了正确的值。一旦该过程完成,则数组最后一个元素的值自然也是最大值,于是就不需要外部循环再次迭代了。由此可见,如果数组中有 N 个数据,则意味着需要迭代 N-1 趟。 每一趟排序过程中,内部循环的任务是查找最小值,以便与 startScan 位置中的值进行交换。在迭代开始之前,minIndex 被设置为 startScan,并且 minValue 被设置为 startScan 位置中的当前值。内部循环然后从 startScan+1 的下标位置开始查找数组中剩余的值。如果它发现一个值要小于当前存储在 minValue 中的值,则使用这个新的更小的值取代 minValue 中原有的值,并且使用新最小值所在的下标取代 minIndex 中存储的下标。 一旦内部循环完成其迭代,则 minIndex 将保存最小元素的下标索引,然后外部循环就会将该元素的内容和 array[startScan] 的内容交换,并且使 startScan 递增 1。请注意,如果未发现比 startScan 位置的值更小的元素,则 minIndex 仍将等于 startScan,那么 startScan 位置中的值就会和它自己交换,实际上就是保持不变。 以下函数使用了选择排序方法,以升序方式排列整数数组中的值。它接收两个参数。第一个形参 array 接收要排序的数组,第二个形参 size 则指示数组中存储了多少个值。 void selectionSort (int array[],int size) { int startScan,minIndex,minValue; for (startScan = 0; startScan < (size - 1); startScan++) { minIndex = startScan; minValue = array[startScan]; for (int index = startScan + 1; index < size; index++) { if (array[index] < minValue) { minValue = array[index]; minIndex = index; } } array[minIndex] = array[startScan]; array[startScan] = minValue; } }如前所述,选择排序需要交换的次数要少于冒泡排序。事实上,正如上例所示,它每一趟只需要交换一个数据。外部循环的每一次迭代都可以将一个值放置到正确的位置,不仅如此,己经正确的值和数组位置在后面的排序中还无须再次检测。 但是,值得注意的是,选择排序不使用标记变量(冒泡排序中的 madeAswap 就是一个标记变量)。这是因为,即使某个数组位置已经保存了下一个最小的值,从而导致它的值在下一趟排序过程中不会改变,但这并不意味着数组已经完成排序,因为其他值可能尚未移动到它们的正确位置。 下面的程序演示了选择排序函数的用法: //This program uses the selection sort algorithm to sort an array in ascending order. #include <iostream> using namespace std; //Function prototypes void selectionSort (int [],int); void showArray(const int [],int); int main() { const int SIZE = 6; // Array of unsorted values int values[SIZE] = {5,7,2,8,9,1}; // Display the values cout << "The unsorted values aren"; showArray(values,SIZE); //Sort the array selectionSort(values,SIZE); // Display the values again cout << "The sorted values aren"; showArray(values,SIZE); return 0; } void selectionSort(int array[],minValue; for (startScan = 0; startScan < (size - 1); startScan++) { minIndex = startScan; minValue = array[startScan]; for(int index = startScan + 1; index < size; index++) { if (array[index] < minValue) { minValue = array[index]; minIndex = index; } } array[minIndex] = array[startScan]; array[startScan] = minValue; } } void showArray(const int array[],int size) { for (int count = 0; count < size; count++) cout << array [count] << " "; cout << endl; }程序输出结果:
The unsorted values are (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |