在一個升序數(shù)組中插入一個數(shù)仍升序輸出
題目舉例：
有一個升序數(shù)組nums，給一個數(shù)字data，將data插入數(shù)組nums中仍舊保證nums升序，返回數(shù)組中有效元素個數(shù)。
比如：nums[100] = {1, 2, 3, 5, 6, 7, 8, 9} size = 8 data = 4
插入之后，nums為{1, 2, 3, 4, 5, 6, 7, 8, 9}
返回 size = 9
方法一：插入排序
1.1方法解析
1.遍歷數(shù)組nums，找到第一個大于等于data的元素位置index。
2.將index及其之后的元素都往后移動一位，騰出位置給數(shù)據(jù)。
3.將data插入到index位置。
4.size加1。
1.2函數(shù)實現(xiàn)
int insertIntoArray(int nums[], int size, int data) {
int i, index;
// 找到第一個大于等于data的元素位置
for (i = 0; i < size; i++) {
if (nums[i] >= data) {
index = i;
break;
}
}
// 將index及其之后的元素都往后移動一位
for (i = size - 1; i >= index; i--) {
nums[i + 1] = nums[i];
}
// 將data插入到index位置
nums[index] = data;
// size加1
size++;
1.3實際代入
void insertIntoArray(int nums[], int size, int data) {
int i, index;
// 找到第一個大于等于data的元素位置
for (i = 0; i < size; i++) {
if (nums[i] >= data) {
index = i;
break;
}
}
// 將index及其之后的元素都往后移動一位
for (i = size - 1; i >= index; i--) {
nums[i + 1] = nums[i];
}
// 將data插入到index位置
nums[index] = data;
// size加1
size++;
for (int i = 0; i < size; i++)
{
printf("%d ", nums[i]);
}
printf("\n");
printf("size = %d", size);
}
int main()
{
int nums[100] = { 1,2,3,5,6,7,8,9 };
int size = 8;
printf("插入前：");
for (int i = 0; i < size; i++)
{
printf("%d ", nums[i]);
}
printf("\nsize = %d\n", size);
int data = 0;
scanf("%d", &data);
printf("插入后：");
Inserdata(nums, size, data);
return 0;
}
1.4運行結(jié)果舉例
方法二 ：二分查找插入排序
2.1方法解析
首先，初始化兩個指針和分別指向數(shù)組的起始和結(jié)束位置。然后進行循環(huán)，直到大于等于為止。在每一次循環(huán)中，計算中間位置，并將中間元素與要插入的值進行比較。leftrightleftrightmid
如果中間元素大于要插入的值，說明要插入的值在左半部分，將指針更新為；
如果中間元素小于要插入的值，說明要插入的值在右半部分，將指針更新為；
如果中間元素等于要插入的值，說明要插入的值已rightmid-1leftmid+1
最終，當大于時，并將要插入的值放入該位置即可。返回數(shù)組大小加1。leftright
2.2函數(shù)實現(xiàn)
void Inserdata(int nums[], int size, int data) //方法二：二分法查找插入排序
{
int left = 0;
int right = size - 1;
while (left < right)
{
int mid = (left + right) / 2;
int midvalue = nums[mid];
if (nums[mid] < data)//找到中間數(shù)和data對比
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
for (int i = size - 1; i >= left; i--)
{
nums[i + 1] = nums[i];
}
nums[left] = data;
size++;
for (int i = 0; i < size; i++)
{
printf("%d ", nums[i]);
}
printf("\n");
printf("size = %d", size);
}
2.3實際代入
void Inserdata(int nums[], int size, int data) //方法二：二分法查找插入排序
{
int left = 0;
int right = size - 1;
while (left < right)
{
int mid = (left + right) / 2;
int midvalue = nums[mid];
if (nums[mid] < data)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
for (int i = size - 1; i >= left; i--)
{
nums[i + 1] = nums[i];
}
nums[left] = data;
size++;
for (int i = 0; i < size; i++)
{
printf("%d ", nums[i]);
}
printf("\n");
printf("size = %d", size);
}
int main()
{
int nums[100] = { 1,2,3,5,6,7,8,9 };
int size = 8;
printf("插入前：");
for (int i = 0; i < size; i++)
{
printf("%d ", nums[i]);
}
printf("\nsize = %d\n", size);
int data = 0;
scanf("%d", &data);
printf("插入后：");
Inserdata(nums, size, data);
return 0;
}
2.4運行結(jié)果舉例
方法三 依次次對比
3.1方法解析
1.數(shù)組為升序
2在數(shù)組中找待插入元素的位置，具體找的方式為
3.從后往前依次與數(shù)組中元素進行比較，如果要插入元素num比end位置數(shù)據(jù)小，則num一定插在end位置之前
4.因此將end位置數(shù)據(jù)往后搬移一個位置
5.如果num大于end位置元素或者end已經(jīng)在區(qū)間最左側(cè)，則位置找到/ 最后將新元素插入到end+1的位置文章來源：http://www.zghlxwxcb.cn/news/detail-637178.html
3.2函數(shù)實現(xiàn)
void Inserdata(int nums[], int size, int data) //方法三：依次對比
{
int end = size - 1;
while (end >= 0 && data < nums[end])
{
nums[end + 1] = nums[end];
end--;
}
nums[end + 1] = data;// 返回插入之后，數(shù)組中有效元素個數(shù)
size++;
for (int i = 0; i < size; i++)
{
printf("%d ", nums[i]);
}
printf("\n");
printf("size = %d", size);
}
3.3實際代入
void Inserdata(int nums[], int size, int data) //方法三：依次對比
{
int end = size - 1;
while (end >= 0 && data < nums[end])
{
nums[end + 1] = nums[end];
end--;
}
nums[end + 1] = data;// 返回插入之后，數(shù)組中有效元素個數(shù)
size++;
for (int i = 0; i < size; i++)
{
printf("%d ", nums[i]);
}
printf("\n");
printf("size = %d", size);
}
int main()
{
int nums[100] = { 1,2,3,5,6,7,8,9 };
int size = 8;
printf("插入前：");
for (int i = 0; i < size; i++)
{
printf("%d ", nums[i]);
}
printf("\nsize = %d\n", size);
int data = 0;
scanf("%d", &data);
printf("插入后：");
Inserdata(nums, size, data);
return 0;
}
3.4運行結(jié)果舉例
文章來源地址http://www.zghlxwxcb.cn/news/detail-637178.html
到了這里，關(guān)于【在一個升序數(shù)組中插入一個數(shù)仍升序輸出】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
