DL Руководство пользователя
Сравнение страницы - Сортировки (v.6 vs v.7)
Ключ
Эти линии были удалены. Это слово было удалено.
Эти линии были добавлены. Это слово было добавлено.

Просмотр истории страницы


Есть 13 изменений. Просмотреть первое изменение .

 Описаны сортировки
  
 1     Сортировка обменом Сортировка с номерами
 2     Сортировка пузырьком - не меняя порядок одинаковых чисел
 3     Сортировка подсчетом (черпаком) - линейная сортировка целых чисел
  
 *Сортировка по возрастанию*
 _bq. ..._
 _bq. int a\[10\];_
 _bq. ..._
 _bq. sort(a,a+10);_
 _bq. ..._
  {quote}_..._
 _int a\[10\];_
 _..._
 _sort(a,a+10);_
 _..._{quote}
  
 *Сортировка по убыванию*
_bq. ..._
 _bq. _{_}int a{_}_\[10\]__;_
 _bq. __..._
 _bq. _{_}sort(a,a+10); reverse(a,a+10); // после сортировки реверсируем массив a_
  {quote}_..._
 _int a{_}_\[10\]__;_
 _..._
 _sort(a,a+10); reverse(a,a+10); // после сортировки реверсируем массив a{_}{quote}
  
 Альтернатива (сортировка по убыванию )
_bq.&nbsp;_{_}sort(a,a+10,greater<int>());_
  {quote}{_}sort(a,a+10,greater<int>());_{quote}
  
 *Сортировка пузырьком* \- не меняя порядок одинаковых чисел
_bq.&nbsp;__..._
 _bq.&nbsp;_{_}int a{_}_\[10\]__;_
 _bq.&nbsp;__..._
 _bq.&nbsp;_{_}stable_sort(a,a+10);_
 _bq.&nbsp;__..._
  {quote}_..._
 _int a{_}_\[10\]__;_
 _..._
 _stable_sort(a,a+10);_
 _..._{quote}
  
 *Сортировка с номерами*
  
 от 0 до 9
  
 ввод
_bq.&nbsp;_{_}int a{_}_\[10\]__,i;_
 _bq.&nbsp;_{_}for (i=0; i<10; i++) cin >> a{_}_\[i\]__;_
  {quote}{_}int a{_}_\[10\]__,i;_
 _for (i=0; i<10; i++) cin >> a{_}_\[i\]__;_{quote}
  
 добавление последней цифрой номера (для двузначных чисел умножаем на 100 и т.д)
_bq.&nbsp;_{_}for (i=0; i<10; i++) a{_}_\[i\]__=a{_}_\[i\]__\*10+i;_
  {quote}{_}for (i=0; i<10; i++) a{_}_\[i\]__=a{_}_\[i\]__\*10+i;_{quote}
  
 Сортируем
_bq.&nbsp;_{_}sort(a,a+10);_
  {quote}{_}sort(a,a+10);_{quote}
  
 Выводим 3 первых номера после сортировки (для двузначных чисел %100 - остаток от деления на 100 и т.д)
_bq.&nbsp;_{_}for (i=0; i<3; i++) cout << (a{_}_\[i\]__%10)+1 << endl;_
  {quote}{_}for (i=0; i<3; i++) cout << (a{_}_\[i\]__%10)+1 << endl;_{quote}
  
 Альтернатива - использование вектора
  
 Для сортировки с номерами можно сделать так:
  
_bq.&nbsp;_{_}vector<pair<int, int> > A(N);_
 _bq.&nbsp;_{_}for (int i = 0; i < N; i++)_
 _bq.&nbsp;_{
 _bq.&nbsp;_cin >> A\[i\].first;
 _bq.&nbsp;_A\[i\].second=i;
 _bq.&nbsp;_};
 \\
  {quote}{_}vector<pair<int, int> > A(N);_
 _for (int i = 0; i < N; i++)_
 cin >> A\[i\].first; \_bq.&nbsp;_A\[i\].second=i;{quote}\\
  
 Выводим 3 первых номера после сортировки
_bq.&nbsp;_{_}for (int i = 0; i < 3; i++) cout << A{_}_\[i\]__.second;_
  {quote}{_}for (int i = 0; i < 3; i++) cout << A{_}_\[i\]__.second;_{quote}
  
 Пусть имеется массив из N точек с координатами x и y
  
 Массив координат точек X,Y сортируется по возрастанию X,&nbsp;а в случае равенства X - по возрастанию Y
 В случае, когда гарантируется, что все X различны,&nbsp;второй массив просто параллельно передвигается&nbsp;никогда не участвуя в сравнениях
  
 Например
_bq.&nbsp;_{_}vector<pair<int, int> > A(N);_
 _bq.&nbsp;_{_}for(int i = 0; i < N; i++)_
 _bq.&nbsp;_{_}cin >> A{_}_\[i\]__.first >> A{_}_\[i\]__.second;_
 _bq.&nbsp;_{_}sort(A.begin(), A.end());_
  {quote}{_}vector<pair<int, int> > A(N);_
 _for(int i = 0; i < N; i++)_
 _cin >> A{_}_\[i\]__.first >> A{_}_\[i\]__.second;_
 _sort(A.begin(), A.end());_{quote}
  
 *Сортировка подсчетом (черпаком)*
 
 {code:title=Cherpak.cpp\|borderStyle=solid}\#include <bits/stdc++.h>using namespace std;
  {code:title=Cherpak.cpp\|borderStyle=solid}
 #include <bits/stdc++.h>using namespace std;
 int main()
 {
  int a[15000],i,n,j;
  for (i=0; i<15000; i++) a[i]=0;
  cin >> n;
  for (i=0; i<n; i++)
  {
  cin >> j;
  a[j]++;
  }
  
  for (i=0; i<15000; i++)
  if (a[i]) for (j=0; j<a[i]; j++) cout << i;
 }{code}
  }
 {code}
Powered by Atlassian Confluence, the Enterprise Wiki. (Version: http://www.atlassian.com/software/confluence Build:#2.6.1 916) - Ошибка/новая особенность - Свяжитесь с Администраторами