7-1 选择排序
时间: 2023-07-02 14:12:07 浏览: 60
选择排序是一种简单直观的排序算法,其基本思想是每次从未排序的元素中选择最小(或最大)的元素,放到已排序的末尾,直到所有元素都被排序。具体实现过程如下:
1. 遍历整个数组,找到最小的元素,将其与第一个元素交换位置。
2. 接着从第二个元素开始遍历数组,找到剩余元素中的最小值,将其与第二个元素交换位置。
3. 重复上述步骤,直到整个数组被排序。
以下是一个 C++ 实现的选择排序代码示例:
```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` 表示数组的长度。`selectionSort` 函数实现了选择排序算法,其中 `minIndex` 表示当前未排序部分中的最小元素的下标。通过不断更新 `minIndex`,找到当前未排序部分中的最小元素,并与当前位置的元素进行交换,直到整个数组被排序。
相关问题
R7-1 选择排序
选择排序是一种简单的排序算法。它的基本思想是每次从未排序的序列中选择最小(或最大)的元素,将其放到已排序序列的末尾,直到所有元素都排完为止。下面是一个使用 C 语言实现的选择排序算法示例:
```c
void selectionSort(int arr[], int n){
int i, j, min_idx;
for (i = 0; i < n-1; i++){
min_idx = i;
for (j = i+1; j < n; j++){
if (arr[j] < arr[min_idx])
min_idx = j;
}
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
```
该算法的时间复杂度为 O(n^2),不适用于大规模数据排序。
7-1冒泡排序csdn
冒泡排序是一种简单直观的排序算法,其基本思想是通过相邻元素之间的比较和交换,将最大的元素逐渐移动到最后的位置。
具体而言,冒泡排序的过程如下:
1. 首先,我们从序列的第一个元素开始,比较其与后续的元素大小;
2. 若第一个元素大于后续元素,则交换两者的位置;
3. 依次比较第二个元素和第三个元素,直到序列的倒数第二个元素;
4. 经过第一轮的比较,最大的元素已经移到了最后的位置;
5. 接下来,我们继续进行第二轮的比较,此时我们只需要比较序列中前n-1个元素,因为最后一个元素已经是最大的;
6. 经过n-1轮的比较和交换,最终序列就按照从小到大的顺序排列好了。
冒泡排序的时间复杂度为O(n^2),其中n为序列的长度。这是因为冒泡排序的每一轮都需要比较n-1次,并且总共需要执行n-1轮。
尽管冒泡排序的时间复杂度较高,但它的实现非常简单,且空间复杂度较低,只需要一个额外的存储空间来交换元素的位置。因此,在一些元素个数较少或者序列基本有序的情况下,冒泡排序仍然是一个不错的选择。
值得注意的是,冒泡排序是一种稳定的排序算法,即相等的元素在排序后的相对位置不会改变。这一点对一些特定需求的排序问题可能是非常重要的。
总之,冒泡排序是一种简单但效率不高的排序算法,适用于一些小规模且简单的排序问题。