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 生日开业蛋糕祝福语简短