Дан целочисленный неотсортированный массив. Например:
4 3 7 0 8 2 5
Максимальный эл-т (т.е. 8) записываем в конец, а все, идущие справа от него, перемещаются влево:
4 3 7 0 2 5 8
Снова запишем максимальный(7) уже на предпоследнее место, (8 не трогаем):
4 3 0 2 5 7 8
И так далее:
3 0 2 4 5 7 8
0 2 3 4 5 7 8
Как Вы оцените эффективность этого алгоритма? Скажите пару слов...
Если Вам покажется, что я недостаточно ясно сформулировал вопрос - пишите, я уточню. Заранее большое спасибо!
Примечание:
Майоров Павел (Павел Майоров)
Почему на массивах свыше 10 000 элементов - бесполезно?
Вот код на С++. Роботает и при миллионе эл-тов:
#include<iostream>
#include<clocale>
using namespace std;
int* grAndSortArray(int *pM, int size)
{
int n=size;
int max=pM[0];
int nmax=0;
for(; n>1; n--)
{
for(int i=0; i<n; i++)
{
if(pM[i]>=max) // найдем максимальный эл-т и его номер
{
max=pM[i];
nmax=i;
}
}
do // передвинем все эл-ты, идущие после максимального, на одну позицию назад
{
pM[nmax++]=pM[nmax+1];
} while(nmax<n);
pM[n-1]=max; // максимальный эл-т запишем в самый конец массива
max=pM[0]; // "сбросим" т.о. переменную, содержащую уже поставленный на место максимальный эл-т
}
return pM;
}
int main()
{
setlocale(LC_ALL,"russian");
int n;
cout<<"Введите размер массива: ";
cin>>n;
int *M=(int*) malloc(n*sizeof(int));
for(unsigned i=0; i<n; i++)
{
//cin>>M[i];
M[i]=rand()%100;
}
cout<<"Массив: ";
for(unsigned i=0; i<n; i++)
{
cout<<M[i]<<' ';
} cout<<endl;
int *sortA=grAndSortArray(M, n);
cout<<"Отсортированный массив: ";
for(unsigned i=0; i<n; i++)
{
cout<<sortA[i]<<' ';
} cout<<endl;
return 0;
}
RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.
Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.
Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.