C++ 將序列前半部分為負整數，後半部分為正整數（數據分類）

一、題目：

將序列前半部分為負整數，後半部分為正整數，不要求排序，但要求盡量減少交換次數。

二、思路：

首先，從數組0開始往後找第一個正整數位置pos;然後，從數組len-1開始往前找第一個負整數位置neg;

接著，交換這兩個數。pos往後找，neg往前找。重複前面步驟，直到pos>=neg結束。

三、實現程序

#include <iostream>

// 交換兩個數

void Swap(int &a, int &b) {

int temp;

temp = a;

a = b;

b = temp;

}

// 將負整數放在左邊，正整數放在右邊

int divPosNeg(int arr[], int len) {

int neg = len-1, pos = 0; // neg,pos分別存儲找到的負整數和正整數的位置

int i, count = 0; // count記錄交換次數

while(pos < neg) {

for(i = pos; i < len; i++) // // 往右掃描，找到第一個正整數

if(arr[i] > 0) {

pos = i;

break;

}

// 從右邊開始找第一個負數

for(int i = neg; i >= 0; i--)

if(arr[i] < 0) {

neg = i;

break;

}

Swap(arr[pos], arr[neg]); // 交換

count++;

pos++;

neg--;

}

return count;

}

int main(int argc, const char * argv[]) {

// insert code here...

int arr[] = {10, 10, -20, 30, 40, -50, 60, -70, 80, -90, -100};

int len, i, count;

len = sizeof(arr) / sizeof(arr[0]); // 獲取整個數組的長度

// 輸出分類前

for(i = 0; i < len; i++)

std::cout << arr[i] << " ";

std::cout << std::endl;

count = divPosNeg(arr, len); // 調用數據分類函數

for(i = 0; i < len; i++)

std::cout << arr[i] << " ";

std::cout << std::endl;

std::cout << "交換的次數：" << count << std::endl;

return 0;

}

運行結果：

---------------------

作者：ChanJose

原文：https://blog.csdn.net/chuanzhouxiao/article/details/85489204

版權聲明：本文為博主原創文章，轉載請附上博文鏈接！

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！