利用以下排序方法实现数组元素排列 1)冒泡法 2)选择法 3)体会两者的区别
时间: 2023-12-03 08:45:09 浏览: 28
1)冒泡法:
冒泡排序是一种简单的排序算法。它重复地遍历要排序的数组,比较相邻的两个元素,如果它们的顺序错误,就交换它们的位置。重复这个过程,直到整个数组都被排序。
以下是冒泡排序的实现过程:
```
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n-1; i++)
// Last i elements are already sorted
for (j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}
```
2)选择法:
选择排序是一种简单的排序算法,它的工作原理如下:首先在未排序的数列中找到最小元素,存放到排序序列的起始位置;然后,再从剩余未排序的元素中继续寻找最小元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
以下是选择排序的实现过程:
```
void selectionSort(int arr[], int n)
{
int i, j, min_idx;
// One by one move boundary of unsorted subarray
for (i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// Swap the found minimum element with the first element
swap(&arr[min_idx], &arr[i]);
}
}
```
3)两者的区别:
冒泡排序和选择排序都是简单的排序算法,但它们的时间复杂度和执行效率略有不同。
冒泡排序的时间复杂度为O(n^2),它是一种稳定的排序算法,它的基本思想是通过相邻元素之间的比较和交换来把小的数交换到数组的前面,大的数交换到数组的后面,从而实现排序。
选择排序的时间复杂度也是O(n^2),它是一种不稳定的排序算法,它的基本思想是每次从未排序的元素中选择一个最小的元素,然后放到已排序序列的末尾,直到所有元素均排序完毕。
冒泡排序的优点是实现简单,容易理解,缺点是排序效率较低,对于大规模数据的排序效率较低。
选择排序的优点是实现简单,排序效率较高,缺点是它是一种不稳定的排序算法,如果要求排序后的序列稳定,不适合使用选择排序。