資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會研究
時尚研究
法律研究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 End deleteSorted(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 << "Element is not present." << 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 Element is not present. 10 20 30 50 70
更新於: 10-Aug-2020
539 次瀏覽
廣告