插入排序,选择排序,起泡排序的特点
时间: 2024-06-19 22:04:30 浏览: 15
插入排序、选择排序和冒泡排序都是比较简单的排序算法,常用于小规模数据的排序。它们的主要特点如下:
1. 插入排序:
插入排序的基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增加1的有序表。
插入排序适用于记录数比较小的排序需求,时间复杂度为O(n^2),但是当记录数比较少时,它的效率还是很高的。
2. 选择排序:
选择排序的基本思想是在未排序的记录中找到最小的记录,将其存放到已排好序的记录序列的末尾,直到所有记录都排好序。
选择排序的时间复杂度也为O(n^2),但是由于每次只需要交换一次记录,因此相对于冒泡排序来说,它交换次数比较少,因此效率略高于冒泡排序。
3. 冒泡排序:
冒泡排序的基本思想是通过相邻元素之间的比较和交换来进行排序,将小的元素逐渐交换到数组前端。
冒泡排序的时间复杂度也为O(n^2),并且由于每次需要交换多次元素,因此效率相对较低。
相关问题
用c++实现排序综合采用插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序)方法实现
好的,以下是用C++实现七种排序算法的代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
// 插入排序
void insertionSort(vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
// 希尔排序
void shellSort(vector<int>& arr) {
int n = arr.size();
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
// 冒泡排序
void bubbleSort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
}
// 快速排序
int partition(vector<int>& arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(vector<int>& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// 选择排序
void selectionSort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
swap(arr[i], arr[min_idx]);
}
}
// 堆排序
void heapify(vector<int>& arr, int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) {
largest = l;
}
if (r < n && arr[r] > arr[largest]) {
largest = r;
}
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(vector<int>& arr) {
int n = arr.size();
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (int i = n - 1; i >= 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
// 归并排序
void merge(vector<int>& arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
vector<int> L(n1);
vector<int> R(n2);
for (int i = 0; i < n1; i++) {
L[i] = arr[l + i];
}
for (int j = 0; j < n2; j++) {
R[j] = arr[m + 1 + j];
}
int i = 0;
int j = 0;
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(vector<int>& arr, int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
int main() {
vector<int> arr = {5, 2, 4, 6, 1, 3};
insertionSort(arr);
for (int i : arr) {
cout << i << " ";
}
cout << endl;
arr = {5, 2, 4, 6, 1, 3};
shellSort(arr);
for (int i : arr) {
cout << i << " ";
}
cout << endl;
arr = {5, 2, 4, 6, 1, 3};
bubbleSort(arr);
for (int i : arr) {
cout << i << " ";
}
cout << endl;
arr = {5, 2, 4, 6, 1, 3};
quickSort(arr, 0, arr.size() - 1);
for (int i : arr) {
cout << i << " ";
}
cout << endl;
arr = {5, 2, 4, 6, 1, 3};
selectionSort(arr);
for (int i : arr) {
cout << i << " ";
}
cout << endl;
arr = {5, 2, 4, 6, 1, 3};
heapSort(arr);
for (int i : arr) {
cout << i << " ";
}
cout << endl;
arr = {5, 2, 4, 6, 1, 3};
mergeSort(arr, 0, arr.size() - 1);
for (int i : arr) {
cout << i << " ";
}
cout << endl;
return 0;
}
```
以上是七种排序算法的代码实现,你可以自行运行并测试。
用dev-c++实现排序综合采用插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序)方法实现
好的,我理解了你的要求。以下是使用 Dev-C++ 实现七种排序算法的示例代码。
```c++
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_SIZE 1000000
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void insertSort(int arr[], int n)
{
for (int i = 1; i < n; i++)
{
int j = i - 1;
int temp = arr[i];
while (j >= 0 && temp < arr[j])
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
void shellSort(int arr[], int n)
{
int gap = n / 2;
while (gap > 0)
{
for (int i = gap; i < n; i++)
{
int j = i - gap;
int temp = arr[i];
while (j >= 0 && temp < arr[j])
{
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = temp;
}
gap /= 2;
}
}
void bubbleSort(int arr[], int n)
{
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
swap(&arr[j], &arr[j + 1]);
}
}
}
}
void quickSort(int arr[], int left, int right)
{
if (left >= right)
{
return;
}
int i = left, j = right, pivot = arr[left];
while (i < j)
{
while (i < j && arr[j] >= pivot)
{
j--;
}
if (i < j)
{
arr[i++] = arr[j];
}
while (i < j && arr[i] < pivot)
{
i++;
}
if (i < j)
{
arr[j--] = arr[i];
}
}
arr[i] = pivot;
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
void selectSort(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;
}
}
if (minIndex != i)
{
swap(&arr[i], &arr[minIndex]);
}
}
}
void adjustHeap(int arr[], int i, int n)
{
int temp = arr[i];
for (int j = i * 2 + 1; j < n; j = j * 2 + 1)
{
if (j + 1 < n && arr[j + 1] > arr[j])
{
j++;
}
if (arr[j] > temp)
{
arr[i] = arr[j];
i = j;
}
else
{
break;
}
}
arr[i] = temp;
}
void heapSort(int arr[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
{
adjustHeap(arr, i, n);
}
for (int i = n - 1; i > 0; i--)
{
swap(&arr[0], &arr[i]);
adjustHeap(arr, 0, i);
}
}
void merge(int arr[], int left, int mid, int right)
{
int *temp = (int *)malloc((right - left + 1) * sizeof(int));
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right)
{
if (arr[i] <= arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
}
}
while (i <= mid)
{
temp[k++] = arr[i++];
}
while (j <= right)
{
temp[k++] = arr[j++];
}
for (int p = 0; p < k; p++)
{
arr[left + p] = temp[p];
}
free(temp);
}
void mergeSort(int arr[], int left, int right)
{
if (left >= right)
{
return;
}
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
int main()
{
int arr[MAX_SIZE];
int n;
printf("请输入数组大小:");
scanf("%d", &n);
printf("请输入数组元素:");
for (int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
clock_t start, end;
double duration;
start = clock();
insertSort(arr, n);
end = clock();
duration = (double)(end - start) / CLOCKS_PER_SEC;
printf("插入排序结果:");
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n插入排序用时:%f秒\n", duration);
start = clock();
shellSort(arr, n);
end = clock();
duration = (double)(end - start) / CLOCKS_PER_SEC;
printf("希尔排序结果:");
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n希尔排序用时:%f秒\n", duration);
start = clock();
bubbleSort(arr, n);
end = clock();
duration = (double)(end - start) / CLOCKS_PER_SEC;
printf("冒泡排序结果:");
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n冒泡排序用时:%f秒\n", duration);
start = clock();
quickSort(arr, 0, n - 1);
end = clock();
duration = (double)(end - start) / CLOCKS_PER_SEC;
printf("快速排序结果:");
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n快速排序用时:%f秒\n", duration);
start = clock();
selectSort(arr, n);
end = clock();
duration = (double)(end - start) / CLOCKS_PER_SEC;
printf("选择排序结果:");
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n选择排序用时:%f秒\n", duration);
start = clock();
heapSort(arr, n);
end = clock();
duration = (double)(end - start) / CLOCKS_PER_SEC;
printf("堆排序结果:");
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n堆排序用时:%f秒\n", duration);
start = clock();
mergeSort(arr, 0, n - 1);
end = clock();
duration = (double)(end - start) / CLOCKS_PER_SEC;
printf("归并排序结果:");
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n归并排序用时:%f秒\n", duration);
return 0;
}
```
你可以将以上代码复制到 Dev-C++ 编辑器中,然后运行该程序即可。程序会提示输入数组大小和数组元素,并输出每种排序算法的结果和用时。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)