- In the body of the first sentence with: small knowledge, big challenge! This paper is participating in the Essentials for programmers “Creative activities
- In the second sentence of the text, add the following words Project Diggin To win the creative gift package and challenge the creative incentive money
What is an algorithm?
Usually learn computer partners often hear the word algorithm, then what is an algorithm? There is no clear definition of algorithm. According to my personal understanding, algorithm is the description of the thinking and steps of solving a specific problem.
In fact, there are a lot of ten algorithms on the Internet, you are very good, the level is very high, so the article is relatively deep, I am a new person. Write this article is also particularly suitable for beginners to learn, simple start.
Ten sorting algorithms
🎈 bubble sort
parsing
Bubbling sort is a basic interchange sort, like the coke we drink, bubbling from the bottom to the top. The way to do this is to move the number bit by bit to one side according to the size of the number, and if you move the small number from the right to the left in the order from the smallest to the largest. For example, sort the five items 3.2.5.8.1 from the smallest to the largest
Code implementation
function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len - 1; i++) {
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j+1]) { // Compare adjacent elements in pairs
var temp = arr[j+1]; // Element swap
arr[j+1] = arr[j]; arr[j] = temp; }}}return arr;
}
Copy the codesample
#include<stdio.h>
int main(a)
{
int n;
scanf("%d",&n);
int a[n+1],ans;
ans=0;
for(int i=1; i<=n; i++)scanf("%d",&a[i]);
for(int i=1; i<=n; i++)for(int j=1; j<=i; j++)if(a[i]<a[j])
ans++;
printf("%d",ans);
}
Copy the code🎈 Selection sort
parsing
Selection sort, as the name implies, selects the smallest (largest) element from all the elements and places it at the beginning of the sequence, and then selects the smallest (largest) element from the remaining queue and places it at the second position. For example, sort the five numbers in 3.2.5.8.1 from smallest to largest.1. Step 1: Select the smallest number from all queues and place it at the top of the sequence
Code implementation
function selectionSort(arr) {
var len = arr.length;
var minIndex, temp;
for (var i = 0; i < len - 1; i++) {
minIndex = i;
for (var j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) { // Find the smallest number
minIndex = j; // Save the smallest index
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
Copy the codesample
#include<iostream>
using namespace std;
int main(a){
int n=0;
long int a[1000] = {0};
cin>>n;
for(int i=0; i<n; i++) cin>>a[i];
for(int i=0; i<n- 1; i++) {
int min_index = i;
for(int j=i; j<n; j++) if(a[j] > a[min_index]) min_index = j;// Find the position of the ith smallest number
swap(a[i],a[min_index]);// Place the ith smallest number in the ith position; If it's just right, you don't have to swap
i++;
for(int j=i; j<n; j++) if(a[j] < a[min_index]) min_index = j;// Find the position of the ith smallest number
swap(a[i],a[min_index]);// Place the ith smallest number in the ith position; If it's just right, you don't have to swap
}
for(int i=0; i<n; i++) cout<<a[i]<<endl;
}
Copy the code🎈 insertion sort
parsing
The idea of insertion sort is to divide the ordered sequence and the unordered sequence, and to insert the numbers in the unordered sequence into the ordered sequence until all the numbers are inserted. For example, sort the five numbers 3.2.5.8.1 from small to large.1. Step 1:3 is an ordered sequence, 2.5.8.1 is an unordered sequence,
Code implementation
function insertionSort(arr) {
var len = arr.length;
var preIndex, current;
for (var i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
return arr;
}
Copy the codesample
After the end of the final examination of the affiliated primary school of Tsinghua University, the results of 30 students were input in math, Chinese and English according to the order of student numbers. The head teacher wanted to know the highest and lowest scores of the three courses, as well as the number of the two students who achieved the highest and lowest scores. (The numbers range from 1 to 30.) Input description The first line input the math scores of 30 students numbered from 1 to 30, separated by Spaces. The second line of input Language results, the third line of input English results output description output four numbers, respectively is the highest total score, the lowest total score, the number of the highest score students, the number of the lowest score students
#include <iostream>
#include <stdlib.h>
using namespace std;
int main(a) {
int*math = new int[3];
int*chinese = new int[3];
int*english = new int[3];
for (int n = 0; n < 3; n++) {
cin >> math[n];
}
for (int n = 0; n < 3; n++) {
cin >> chinese[n];
}
for (int n = 0; n < 3; n++) {
cin >> english[n];
}
int*sum= new int[3];
int*order = new int[3];
for (int n = 0; n < 3; n++) {
sum[n] = math[n] + chinese[n] + english[n];
}
for (int n = 0; n <= 2; n++) {
order[n] = sum[n];
}
for (int n = 1; n <=2; n++){
int now = sum[n], space = 0;
while (now > sum[space])
space++;
for (int i = n; i > space; i--)
sum[i] = sum[i - 1];
sum[space] = now;
}
int max, min;
for (int n = 0; n <= 2; n++) {
if (order[2] == sum[n])
max = n;
if (order[0] == sum[n])
min = n;
}
cout << sum[2] < <endl;
cout << sum[0] < <endl;
cout << max<<endl;
cout << min<<endl;
system("pause");
return 0;
}
Copy the code🎈 Hill sort
parsing
The main idea of Hill sort is to group the data, and then perform insertion sort for each group of data. After each group of data is in order, all the groups are sorted by insertion sort for the last time. Can be said to be an upgrade to insert sort, by reducing the number of data exchanges, in order to achieve the speed of sorting. For example, sort the six numbers in 3.2.5.8.1.6 from the smallest to the largest.1. Step 1: Divide the six numbers into three groups according to two groups.
Code implementation
function shellSort(arr) {
var len = arr.length;
for (var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
// Note: this is different from the GIF, which is executed in groups. In practice, multiple groups are executed alternately
for (var i = gap; i < len; i++) {
var j = i;
var current = arr[i];
while (j - gap >= 0&& current < arr[j - gap]) { arr[j] = arr[j - gap]; j = j - gap; } arr[j] = current; }}return arr;
}
Copy the codesample
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int main(a)
{
int n,k,i,a[100001],b[100001],ans=0;
scanf("%d%d",&n,&k);
for(i=1; i<=n; i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);//sort sort from smallest to largest
for(i=1; i<=n- 1; i++) b[i]=a[i+1]-a[i];// Calculate the difference between different levels of players
sort(b+1,b+n);//sort sort from smallest to largest
for(i=1; i<=k; i++) ans+=b[i];// Find the sum of the first K level differences
printf("%d",ans);/ / output
return 0;
}
Copy the code🎈 merge sort
parsing
The main idea of merge sort is to classify the elements of the whole sequence layer by layer, then compare and sort from the smallest group, merge into a large group, proceed layer by layer, and finally all the elements are ordered. For example, sort the six numbers in 3.2.5.8.1.6 from smallest to largest.1. Step 1: Divide two groups into three groups.
Code implementation
function mergeSort(arr) {
var len = arr.length;
if (len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
var result = [];
while (left.length>0 && right.length>0) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else{ result.push(right.shift()); }}while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}
Copy the codesample
#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
using namespace std;
string s;
map<string.int>nmsl;
int n;
long long ans=0;
int c[1000001],d[1000001];
void qsort(int a,int b)
{
if(a==b)return;
int mid=(a+b)>>1;
int i=a,j=mid+1,k=a;
qsort(a,mid),qsort(mid+1,b);
while(i<=mid&&j<=b)
if(c[i]<=c[j])
{
d[k++]=c[i++];
}
else
{
d[k++]=c[j++];
ans+=mid-i+1;
}
while(i<=mid)
d[k++]=c[i++];
while(j<=b)
d[k++]=c[j++];
for(intl=a; l<=b; l++) c[l]=d[l]; }int main(a)
{
scanf("%d",&n);
for(int i=1; i<=n; i++) {cin>>s;
nmsl[s]=i;
}
int j=0;
for(int i=1; i<=n; i++) {cin>>s;
c[++j]=nmsl[s];
}
qsort(1,n);
printf("%lld",ans);
return 0;
}
Copy the code🎈 quicksort
parsing
Quicksort firstly takes a number from the sequence as the base number. In the partitioning process, all numbers larger than this number are placed to its right, and all numbers less than or equal to this number are placed to its left. Then repeat the second step for the left and right intervals until there is only one number in each interval. Step 1: Take 3 as the base number, move to the right for those smaller than 3 and move to the left for those smaller than 3
Code implementation
function quickSort(arr, left, right) { var len = arr.length, partitionIndex, left = typeof left ! ='number' ? 0: left, right = typeof right ! ='number' ? len - 1 : right;
if (left < right) {
partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex- 1);
quickSort(arr, partitionIndex+1, right);
}
return arr;
}
function partition(arr, left ,right) { // Partition operations
var pivot = left, // Set the pivot value
index = pivot + 1;
for (var i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index- 1;
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
Copy the codesample
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<bits/stdc++.h>
int n;
int ans=0;
int i,j,k;
int a[100010];
using namespace std;
int main(a){
cin>>n;
j=0;
for(i=1; i<=n; i++)cin>>a[i];
sort(a,a+n+1);// Sort from smallest to largest
ans=n+a[n]*10;// The amount of time each person needs and the amount of time it takes to get on and off the elevator
for(i=1; i<=n; i++){if(a[i]! =a[i- 1]) {// At the beginning of the loop, the array defaults to 0 to avoid missing all at the same level
ans=ans+5;// Lifts need switches}}cout<<ans;
return 0;
}
Copy the code🎈 counting sort
parsing
Counting sort is a sorting algorithm that is not based on comparison. Its core is to convert the input data values into keys and store them in the extra array space to achieve sorting effect. Example: Sort the six numbers of 3.2.5.8.1.6 from the smallest to the largest by 1. Step 1: Determine the maximum and minimum number of all elements to be sorted
Code implementation
function countingSort(arr, maxValue) {
var bucket = new Array(maxValue + 1),
sortedIndex = 0;
arrLen = arr.length,
bucketLen = maxValue + 1;
for (var i = 0; i < arrLen; i++) {
if(! bucket[arr[i]]) { bucket[arr[i]] =0;
}
bucket[arr[i]]++;
}
for (var j = 0; j < bucketLen; j++) {
while(bucket[j] > 0) { arr[sortedIndex++] = j; bucket[j]--; }}return arr;
}
Copy the codesample
#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <string>
#include <algorithm>
#include <list>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
using namespace std;
int const maxk = 1000005,maxn = 1000005;
// Interface: a[I] original array. Ranked [I] specifies the number of ordered arrays to use, and the maxK range of numbers
/ / call jishusort (n, maxk); //n represents the size of the array
int a[maxn],ranked[maxn],cnt[maxk];// CNT [I] is less than or equal to I
void jishusort(int n,int k)// The size of the n array and the range of numbers in the k array
{
for(int i = 0; i < n; i ++)
{
cnt[a[i] + 500000] + +; }for(int i = 1; i < k; i ++)
{
cnt[i] += cnt[i - 1];
}
for(int i = n - 1 ; i >= 0; i --)
{
ranked[--cnt[a[i]+ 500000]] = a[i]; }}int main(a)
{
//freopen("in.txt","r",stdin);
int n,m;
while(scanf("%d%d",&n,&m)! = EOF){memset(cnt,0.sizeof(cnt));
for(int i = 0; i < n; i ++)
{
scanf("%d",&a[i]);
}
jishusort(n,maxk);
for(int i = n - 1; i > n - m; i --)
{
printf("%d ",ranked[i]);
}
printf("%d\n",ranked[n - m]);
}
return 0;
}
// Forget multiple sets of data
// Forget to empty
Copy the code🎈 radix sort
parsing
Radix sort is to unify each element of the sequence to be sorted into the element with the same length of digits. The element with the short digit reaches the same length by adding 0, and then carries out stable counting sort from the lowest digit or the highest digit, and finally forms an ordered sequence. Radix sort is mainly sort for integers. Since integers can also represent strings or floating-point numbers in a particular format, other data types that can be expressed by integers can also use radix sort. For example, sort the array {53, 3, 542, 748, 14, 214} in ascending order using radix sort. Round 1 sort [in ones place]: Note: Prepare 10 arrays (10 buckets) in advance, 0-9 corresponding to the number of 0-9 (1) put each number in the corresponding array according to the size of the bits (2) and then take out the first round of sorting from the 0-9 array/bucket according to the sequence of elements added: 542 53 3 14 214 748
Code implementation
var counter = [];
function radixSort(arr, maxDigit) {
var mod = 10;
var dev = 1;
for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
for(var j = 0; j < arr.length; j++) {
var bucket = parseInt((arr[j] % mod) / dev);
if(counter[bucket]==null) {
counter[bucket] = [];
}
counter[bucket].push(arr[j]);
}
var pos = 0;
for(var j = 0; j < counter.length; j++) {
var value = null;
if(counter[j]! =null) {while((value = counter[j].shift()) ! = null) { arr[pos++] = value; }}}}return arr;
}
Copy the codesample
#include <cstdio>
#include <algorithm>
#define int long long
struct node {
int id, v;
inline bool operator < (const node x) const {returnv < x.v; } } b[300005];
inline bool operator < (const int x, const node y) {returnx < y.v; }int a[300005], c[300005], s[300005], n, N;
inline void update(const int x) {
for (int i(x); i <= n; i += (i & ~i + 1)) ++ c[i];
}
inline int query(const int x) {
int sum(0);
for (int i(x); i; i -= (i & ~i + 1)) sum += c[i];
return sum;
}
signed main(a) {
int m, last(0);
scanf("%lld%lld", &n, &m);
for (int i(1); i <= n; ++ i) scanf("%lld", &b[i].v), b[i].id = i;
std::sort(b + 1, b + n + 1);
a[b[1].id] = 1;
for (int i(2); i <= n; ++ i) a[b[i].id] = (b[i].v ! = b[i -1].v) + a[b[i - 1].id];
for (int i(n); i >= 1; -- i)
s[a[i]] += query(a[i]), update(a[i]);
N = a[b[n].id];
for (int i(2); i <= N; ++ i) s[i] += s[i - 1];
printf("%lld\n", s[N]);
a[0] = -0x3fffffff;
while (m --) {
int k;
scanf("%lld", &k);
if (a[k] < a[last]) k = last;
last = k;
printf("%lld\n", s[N] - s[a[k]]);
}
return 0;
}
Copy the code🎈 heap sort
parsing
Heap sort is the use of binary heap concept to sort the selection of sorting algorithm, divided into two kinds: ascending sort: using the maximum heap to sort descending sort: using the minimum heap to sort example: add a GIF we see more clearly
Code implementation
var len; // Since multiple declared functions require data length, len is set as a global variable
function buildMaxHeap(arr) { // Create a big top heap
len = arr.length;
for (var i = Math.floor(len/2); i >= 0; i--) { heapify(arr, i); }}function heapify(arr, i) { / / heap of adjustment
var left = 2 * i + 1,
right = 2 * i + 2,
largest = i;
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, largest);
}
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function heapSort(arr) {
buildMaxHeap(arr);
for (var i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0);
}
return arr;
}
Copy the codesample
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
priority_queue<ll,vector<ll>,greater<ll> > a;// Call the priority queue directly
#define in(t) freopen("t.in"."r",stdin)
#define out(t) freopen("t.out"."w",stdout)
#define m(a) memset(a,0,sizeof(a))
int main(a){
long long ans=0,n,t;// long long; // long long
scanf("%lld",&n);
for(int i=1; i<=n; i++){scanf("%lld",&t);
a.push(t);
}
for(int i=1; i<=n- 1; i++){int c,d;
c=a.top();
a.pop();
d=a.top();
a.pop();// Take the smallest two numbers each time
ans+=c+d;// Add energy
a.push(c+d);
}// It is the same as merging fruit
printf("%lld",ans);
return 0;
}
Copy the code🎈 bucket sort
parsing
Bucket sort is an updated version of counting sort, sorting data into a finite number of buckets, and then sorting each bucket separately. Example:
Code implementation
function bucketSort(arr, bucketSize) {
if (arr.length === 0) {
return arr;
}
var i;
var minValue = arr[0];
var maxValue = arr[0];
for (i = 1; i < arr.length; i++) {
if (arr[i] < minValue) {
minValue = arr[i]; // The minimum value of input data
} else if (arr[i] > maxValue) {
maxValue = arr[i]; // The maximum value of the input data}}// Initialize the bucket
var DEFAULT_BUCKET_SIZE = 5; // Set the default number of buckets to 5
bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
var buckets = new Array(bucketCount);
for (i = 0; i < buckets.length; i++) {
buckets[i] = [];
}
// Allocate data to buckets using mapping functions
for (i = 0; i < arr.length; i++) {
buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
}
arr.length = 0;
for (i = 0; i < buckets.length; i++) {
insertionSort(buckets[i]); // Sort each bucket, using insert sort
for (var j = 0; j < buckets[i].length; j++) { arr.push(buckets[i][j]); }}return arr;
}
Copy the codesample
#include <bits/stdc++.h>
const int MAXN=5000005;
int n,m,i,j,k=3,x,y,a[MAXN],b[MAXN];
//x is for "shrink potions",y is for minimum cost, and b is for bucket sorting
inline void read(int &x) / / read fast
{
short negative=1;
x=0;
char c=getchar();
while(c<'0' || c>'9')
{
if(c==The '-')
negative=- 1;
c=getchar();
}
while(c>='0' && c<='9')
x=(x<<3)+(x<<1)+(c^48),c=getchar();
x*=negative;
}
inline void print(int x) / / are about to lose
{
if (x<0)
putchar(The '-'),x=-x;
if (x>9)
print(x/10);
putchar(x%10+'0');
}
signed main(void)
{
read(n),read(m);
for (i=1; i<=n; i++) read(a[i]),b[a[i]]++;for (i=1; i<=30000; i++)/ / bucket sorting
while (b[i])
a[++j]=i,b[i]--;
for (i=1; i<=n; i++) {bool f=false;
while (a[i]>k) // When you have to use "shrink potions"
{
if (m<=0) // Try to use the "shrink potion" effect and exit at the end of a run rather than once m is less than or equal to 0
{
f=true;
break;
}
x++,y++,k+=3; // Use the shrink potion once
}
if (f)
break;
y+=(a[i]<k)?1:4; // Determine whether the fee is 1 or 4
m-=(a[i]%3)? (a[i]%3) :3; // Here we use the button directly from m
}
if (m>0) // Pull all minions or A does not attack it
return printf("Human Cannot Win Dog"),0;
for (i=1; i<=n && m<0; i++)if (a[i]%3= =0 && a[i]<=k && m+3< =0)
y-=4,m+=3;
for (i=1; i<=n && m<0; i++)if (a[i]%3= =1 && a[i]<=k && m+1< =0)
y-=1,m+=1;
for (i=1; i<=n && m<0; i++)if (a[i]%3= =2 && a[i]<=k && m+2< =0)
y-=1,m+=2;
// First 3, then 2, then 1
print(x),putchar(' '),print(y);
return 0;
}
Copy the codeTime complexity of ten sorting algorithms
Conclusion:
Due to my limited ability, if the article error, welcome comments correction. If this article is helpful to you, I hope you can leave a “like” to support it. Thank you!
