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