若序列 (24, 90, 14, 55, 31, 36) 分别采用简单选择排序法 、快速排序算法(按照值的大小从小到大)进行排序,求排序过程和排序结果(分别写出每一趟排序的结果)。
时间: 2024-05-21 17:16:11 浏览: 9
采用简单选择排序法进行排序:
首先,在序列中找到最小的元素,将其放置在首位,然后在剩余的元素中再次找到最小元素,将其放置在已排序序列的末尾,以此类推,直到所有元素都排好序为止。
第一趟排序:14 90 24 55 31 36
第二趟排序:14 24 90 55 31 36
第三趟排序:14 24 31 55 90 36
第四趟排序:14 24 31 36 90 55
第五趟排序:14 24 31 36 55 90
第六趟排序:14 24 31 36 55 90
因此,最终的排序结果为:14 24 31 36 55 90。
采用快速排序算法进行排序:
快速排序算法的基本思想是通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,然后再按此方法对这两部分记录继续进行排序,以达到整个序列有序的目的。
首先,选取一个基准元素(一般选取序列的第一个元素),将序列中比基准元素小的元素放置在其左边,比基准元素大的元素放置在其右边。然后,对左右两个子序列分别进行快速排序,直到所有子序列都只有一个元素为止。
第一趟排序:14 24 36 55 31 90
第二趟排序:14 24 31 55 36 90
第三趟排序:14 24 31 36 55 90
因此,最终的排序结果为:14 24 31 36 55 90。
相关问题
简单选择排序和快速排序的算法设计思想
简单选择排序的算法设计思想是:每次从未排序的序列中选择最小的元素,将其放到已排序序列的末尾。具体实现时,可以通过遍历未排序序列,找到最小元素的位置,然后将其与未排序序列的第一个元素交换位置,即可完成一次选择排序。
快速排序的算法设计思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,然后再分别对这两部分记录继续进行排序,直到整个序列有序。具体实现时,可以通过选取一个基准元素,将序列中小于基准元素的元素放在基准元素的左边,大于基准元素的元素放在基准元素的右边,然后递归地对左右两个子序列进行快速排序。
针对一无序序列(自定义),采用快速排序算法,实现排序
好的,针对一无序序列,我来告诉你如何使用快速排序算法进行排序。首先,我们需要了解快速排序算法的基本思想:
快速排序是一种分治策略的排序算法,基本思路是:选定一个基准数,将比基准数小的数全部放在基准数的左边,比基准数大的数全部放在基准数的右边,然后再递归地对左右两个子序列进行排序,直到整个序列有序为止。
接下来,我们可以根据这个思路写出快速排序算法的代码实现:
```
void quickSort(int arr[], int left, int right) {
if (left >= right) {
return;
}
int i = left, j = right;
int pivot = arr[(left + right) / 2]; // 选取基准数
while (i <= j) {
while (arr[i] < pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i <= j) {
swap(arr[i], arr[j]);
i++;
j--;
}
}
quickSort(arr, left, j); // 递归排序左子序列
quickSort(arr, i, right); // 递归排序右子序列
}
```
这里的 arr 表示待排序的数组,left 和 right 分别表示当前排序区间的左右边界。在算法中,我们先选取基准数 pivot,然后用双指针 i 和 j 分别从左右两端向中间扫描,如果左边的数小于 pivot,就继续向右移动 i 指针;如果右边的数大于 pivot,就继续向左移动 j 指针;如果 i 指针指向的数大于等于 pivot,且 j 指针指向的数小于等于 pivot,就交换 i 和 j 指针所指向的数。这样一趟下来,就能够将基准数放到它最终的位置上,同时也将序列分成了两个子序列,通过递归地对左右两个子序列进行排序,最终实现了对整个序列的排序。
最后,我们可以在程序中调用 quickSort 函数对序列进行排序,如下所示:
```
int main() {
int arr[] = {5, 3, 8, 4, 2, 7, 1, 6};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
```
这里的 arr 数组即为待排序的数组,n 表示数组的长度,我们将调用 quickSort 函数对它进行排序,最终输出有序的数组。