C ++中的排序数组
在这里，我们将看到排序数组的一些基本概念。数组是同类数据结构，可以在某些连续的内存位置中保存相同类型的数据。有时我们需要对元素进行排序以使用它们。除此之外，我们可以创建一个排序数组。那将总是被排序。
在这种情况下，我们将看到用于插入和删除到排序数组中的算法。如果我们在其中插入一些元素，它将自动放置在已排序的位置。因此，插入后我们无需再次对其进行排序。当我们删除时，它将删除元素，并通过向右移动元素来填充空白区域。由于我们使用的是排序数组，因此在删除元素之前，我们将使用二进制搜索算法查找该元素。
算法
insertSorted(arr, n, key):Begin
if n >= max size of the array, then return
otherwise i := n – 1
while i >= 0 and arr[i] > key, do
arr[i + 1] := arr[i]
i := i - 1
done
arr[i + 1] := key
n := n + 1
EnddeleteSorted(arr, n, key):Begin
pos := search key into arr
if pos is -1, then item is not found, and return
otherwise i := pos
while i < n – 1, do
arr[i] := arr[i + 1]
i := i + 1
done
n := n + 1
End示例
#include <iostream>
#define MAX 10
using namespace std;
void display(int arr[], int n){
for(int i = 0; i <n; i++){
cout << arr[i] << " ";
}
cout << endl;
}
int search(int arr[], int low, int high, int key){
if (high < low)
return -1;
int mid = (low + high) / 2; /*low + (high - low)/2;*/
if (key == arr[mid])
return mid;
if (key > arr[mid])
return search(arr, (mid + 1), high, key);
return search(arr, low, (mid - 1), key);
}
void insertSorted(int arr[], int &n, int key){
if (n >= MAX){
cout << "No place to insert";
return;
}
int i;
for (i = n - 1; (i >= 0 && arr[i] > key); i--)
arr[i + 1] = arr[i];
arr[i + 1] = key;
n = n + 1;
}
void deleteSorted(int arr[], int &n, int key){
int key_pos = search(arr, 0, n, key);
if(key_pos == -1){
cout << "元素不存在。" << endl;
return;
}
int i;
for (i = key_pos; i < n - 1; i++)
arr[i] = arr[i + 1];
n = n - 1;
}
int main() {
int arr[MAX];
int n = 0;
insertSorted(arr, n, 10);
insertSorted(arr, n, 20);
insertSorted(arr, n, 30);
insertSorted(arr, n, 40);
insertSorted(arr, n, 50);
insertSorted(arr, n, 60);
insertSorted(arr, n, 70);
display(arr, n);
deleteSorted(arr, n, 35);
deleteSorted(arr, n, 40);
deleteSorted(arr, n, 60);
display(arr, n);
}输出结果
10 20 30 40 50 60 70 元素不存在。 10 20 30 50 70
热门推荐
10 小红书平安祝福语简短
11 生日祝福语大全女孩简短
12 收生日红包祝福语 简短
13 领证幽默祝福语简短
14 法考面试祝福语简短
15 老哥出门祝福语简短语
16 送灯祝福语简短独特
17 幼儿狗年祝福语大全简短
18 好听的元旦简短祝福语