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 赚钱的祝福语女生简短