10種類のソートアルゴリズムのまとめ(バブル、選択、挿入、ヒル、集計、高速、スタック、トポロジー、選手権、基数)
48251 ワード
- ， 。 ， ：
- （1）
- （2）
- （3）
- ，（1）（2） ， （3）； ，（1） 。
-
- ：
- 、 （Bubble） ——
- 、 —— /
- 、 ——
- 、 （Shell） ——
- 、
- 、
- 、
- 、
- 、
- 、
-
-
-
- 、 （Bubble）
-
- ----------------------------------Code n ------------------------------------
- void BubbleSortArray()
- {
- for(int i=1;i<n;i++)
- {
- for(int j=0;i<n-i;j++)
- {
- if(a[j]>a[j+1])//
- {
- int temp;
- temp=a[j]; a[j]=a[j+1]; a[j+1]=temp;
- }
- }
- }
- }
- -------------------------------------------------Code------------------------------------------------
- O（n²）, 。
-
-
- 、
- ----------------------------------Code n --------------------------------
- void SelectSortArray()
- {
- int min_index;
- for(int i=0;i<n-1;i++)
- {
- min_index=i;
- for(int j=i+1;j<n;j++)//
- if(arr[j]<arr[min_index]) min_index=j;
- if(min_index!=i)// ，
- {
- int temp;
- temp=arr[i]; arr[i]=arr[min_index]; arr[min_index]=temp;
- }
- }
- }
- -------------------------------------------------Code-----------------------------------------
- O（n²）， 。
-
-
- 、
- --------------------------------------------Code n -------------------------------------
- void InsertSortArray()
- {
- for(int i=1;i<n;i++)// ， arr[0]
- {
- int temp=arr[i];//temp
- int j=i-1;
- while (j>=0 && arr[j]>temp)/* temp ， temp */
- {
- arr[j+1]=arr[j];
- j--;
- }
- arr[j+1]=temp;
- }
- }
- ------------------------------Code--------------------------------------------------------------
- O（n）； O（n²） 、 ，
- ， 、 。
-
-
- 、 （Shell） ——
- -------------------------------------Code n -------------------------------------
- void ShellSortArray()
- {
- for(int incr=3;incr<0;incr--)// ， 3，2，1
- {
- for(int L=0;L<(n-1)/incr;L++)//
- {
- for(int i=L+incr;i<n;i+=incr)//
- {
- int temp=arr[i];
- int j=i-incr;
- while(j>=0&&arr[j]>temp)
- {
- arr[j+incr]=arr[j];
- j-=incr;
- }
- arr[j+incr]=temp;
- }
- }
- }
- }
- --------------------------------------Code-------------------------------------------
- 。
- O（nlog2^n）~O（n^1.5）， 。 ， 2 ， 。
- （Shell） ， 。 ， 。
-
-
- 、
- ----------------------------------------------Code ---------------------------------------
- void MergeSort(int low,int high)
- {
- if(low>=high) return;//
- else int mid=(low+high)/2;/* , ， */
- MergeSort(low,mid);//
- MergeSort(mid+1,high);
- int [] B=new int [high-low+1];// ，
- for(int i=low,j=mid+1,k=low;i<=mid && j<=high;k++)/* ， */
- {
- if (arr[i]<=arr[j];)
- {
- B[k]=arr[i];
- I++;
- }
- else
- { B[k]=arr[j]; j++; }
- }
- for( ;j<=high;j++,k++)// ，
- B[k]=arr[j];
- for( ;i<=mid;i++,k++)// ，
- B[k]=arr[i];
- for(int z=0;z<high-low+1;z++)// B arr
- arr[z]=B[z];
- }
- -----------------------------------------------------Code---------------------------------------------------
- O（nlogn）， 、 。
- ， 。
-
- 、
- ------------------------------------Code--------------------------------------------
- /* ： ， ， ， ， 。*/ void swap(int a,int b){int t;t =a ;a =b ;b =t ;}
- int Partition(int [] arr,int low,int high)
- {
- int pivot=arr[low];//
- while (low < high)
- {
- //
- while (low < high && arr[high] >= pivot)
- {
- --high;
- }
- //
- swap(arr[low], arr[high]);
- //
- while (low <high &&arr [low ]<=pivot )
- {
- ++low ;
- }
- swap (arr [low ],arr [high ]);//
- }
- return low ;//
- }
- void QuickSort(int [] a,int low,int high)
- {
- if (low <high )
- {
- int n=Partition (a ,low ,high );
- QuickSort (a ,low ,n );
- QuickSort (a ,n +1,high );
- }
- }
- ----------------------------------------Code-------------------------------------
- O（nlogn）， 。
- ； ， O（n²） 。 ， 。 ， O（nlogn）。
- 。
-
-
-
- 、
- ： 、 ， 。
- ：
- (1) i=l, temp＝ kl ;
- (2) i j=2i+1;
- (3) j<＝n－1， (4), (6);
- (4) kj kj+1, kj+1>kj, j＝j＋1， j ；
- (5) temp kj， kj>temp， ki kj， i=j,j=2i+1, (3), (6)
- (6) ki temp， 。
- -----------------------------------------Code---------------------------
- void HeapSort(SeqIAst R)
-
- { // R[1..n] ， R[0] int I; BuildHeap(R)； // R[1-n] for(i=n;i>1；i--) // R[1..i] ， n-1 。{ R[0]=R[1]; R[1]=R[i]; R[i]=R[0]; // Heapify(R,1,i-1); // R[1..i-1] ， R[1] } } ---------------------------------------Code--------------------------------------
-
-
- ， ， Heapify 。
-
- O(nlgn)。 。 ， 。 ， O(1)， 。
-
-
- :
- ， R[1..n] ， n-1 ， R[2..n] ， n-2 。 ， n-2 ， n-1 ， ， 。
- ， 。
-
-
- 、
- ：
- ： 。
- ：
-
-
- ， （ ）， （ ） 。
- ---------------------------------------Code--------------------------------------
- void TopologicalSort()/* 。 G ， G OK， ERROR*/
- {
- int indegree[M];
- int i,k,j;
- char n;
- int count=0;
- Stack thestack;
- FindInDegree(G,indegree);// indegree[0....num]
- InitStack(thestack);//
- for(i=0;i<G.num;i++)
- Console.WriteLine(" "+G.vertices[i].data+" "+indegree[i]);
- for(i=0;i<G.num;i++)
- {
- if(indegree[i]==0)
- Push(thestack.vertices[i]);
- }
- Console.Write(" ：");
- while(thestack.Peek()!=null)
- {
- Pop(thestack.Peek());
- j=locatevex(G,n);
- if (j==-2)
- {
- Console.WriteLine(" ， 。");
- exit();
- }
- Console.Write(G.vertices[j].data);
- count++;
- for(p=G.vertices[j].firstarc;p!=NULL;p=p.nextarc)
- {
- k=p.adjvex;
- if (!(--indegree[k]))
- Push(G.vertices[k]);
- }
- }
- if (count<G.num)
- Cosole.WriteLine(" ， ， 。");
- else
- Console.WriteLine(" 。");
- }
- ----------------------------------------Code--------------------------------------
- O（n+e）。
-
-
-
- 、
- 。
- n ， ， n／2 ( )， ，
- n／2 ， ，…， ， 。
-
-
-
- --------------------------------Code in C---------------------------------------
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #include <math.h>
- #define SIZE 100000
- #define MAX 1000000
- struct node
- {
- long num;//
- char str[10];
- int lastwin;//
- int killer;//
- long times;//
- }data[SIZE];
- long CompareNum=0;
- long ExchangeNum=0;
- long Read(char name[])// a.txt ， data[] ；
- {
- FILE *fp;
- long i=1;
- fp=fopen(name,"rw");
- fscanf(fp,"%d%s",&data[i].num,data[i].str);
- while(!feof(fp))
- {
- i++;
- fscanf(fp,"%d%s",&data[i].num,data[i].str);
- }
- return (i-1);
- }
- long Create(long num)// ， （ ） data[]
- {
- int i,j1,j2,max,time=1;
- long min;//
- for(i=1;pow(2,i-1)<num;i++)
- ;
- max=pow(2,i-1);//
- for(i=1;i<=max;i++)//
- {
- data[i].killer=0;
- data[i].lastwin=0;
- data[i].times=0;
- if(i>num)
- data[i].num=MAX;
- }
- for(i=1;i<=max;i+=2)//
- {
- ++CompareNum;
- if(data[i].num <= data[i+1].num)
- {
- data[i].lastwin = i+1;
- data[i+1].killer=i;
- ++data[i].times;
- ++data[i+1].times;
- min=i;
- }
- else
- {
- data[i+1].lastwin=i;
- data[i].killer=i+1;
- ++data[i].times;
- ++data[i+1].times;
- min=i+1;
- }
- }
- j1=j2=0;//
- while(time <= (log(max)/log(2)))//
- {
- for(i=1;i<=max;i++)
- {
- if(data[i].times==time && data[i].killer==0)//
- {
- j2=i;//
- if(j1==0)// ，
- j1=j2;
- else// ，
- {
- ++CompareNum;
- if(data[j1].num <= data[j2].num)//
- {
- data[j1].lastwin = j2;// j2
- data[j2].killer=j1;//j2 j1
- ++data[j1].times;
- ++data[j2].times;// 1
- min=j1;// j1
- j1=j2=0;// j1，j2 0
- }
- else//
- {
- data[j2].lastwin=j1;
- data[j1].killer=j2;
- ++data[j1].times;
- ++data[j2].times;
- min=j2;
- j1=j2=0;
- }
- }
- }
-
- }
- time++;// 1
- }
- return min;//
- }
- void TournamentSort(long num)//
- {
- long tag=Create(num);//
- FILE *fp1;
- fp1=fopen("sort.txt","w+");// sort.txt
- while(data[tag].num != MAX)//
- {
- printf("%d %s
",data[tag].num,data[tag].str);//
- fprintf(fp1,"%d %s
",data[tag].num,data[tag].str);//
- data[tag].num=MAX;//
- tag=Create(num);//
- }
- }
- int main()
- {
- int num;
- char name[10];
- printf("Input name of the file:");
- gets(name);
- num=Read(name);//
- TournamentSort(num);//
- printf("CompareNum=%d
ExchangeNum=%d
",CompareNum,ExchangeNum);
- return 0;
- }
- ------------------------------------------Code-------------------------------------
-
-
- 、
- 。 ， 。
- ， ；
- “ ” ， “ ” 。
- “ ” “ ” ， 。
- ———————————————————————————————————————
- ：
- “ ”： 。 ：
- ：§＜¨＜©＜ª
- ：2＜3＜……＜K＜A
- ， ； 。 ， ， ：
- §2，…，§A，¨2，…，¨A，©2，…，©A，ª2，…，ªA
- ， 。
- ： （ ）， ， 。
- ： （ ）， ， （ ）， 。
- ———————————————————————————————————————
- ：
- (Most Significant Digit first) ， MSD ： k1 ， ， k1 ， k2 ， ， ， kd 。 ， 。
- (Least Significant Digit first) ， LSD ： kd ， kd-1 ， ， k1 。
- ---------------------------------Code in C#------------------------------------------
- using System;
- using System.Collections.Generic;
- using System.Linq;
- using System.Text;
- namespace LearnSort
- {
- class Program
- {
- static void Main(string[] args)
- {
- int[] arr = CreateRandomArray(10);//
- Print(arr);//
- RadixSort(ref arr);//
- Print(arr);//
- Console.ReadKey();
- }
- public static void RadixSort(ref int[] arr)
- {
- int iMaxLength = GetMaxLength(arr);
- RadixSort(ref arr, iMaxLength);
- }
- private static void RadixSort(ref int[] arr, int iMaxLength)
- {
- List<int> list = new List<int>();//
- List<int>[] listArr = new List<int>[10];//
- char currnetChar;// 123 2
- string currentItem;// 123
- for (int i = 0; i < listArr.Length; i++)// 。
- listArr[i] = new List<int>();
- for (int i = 0; i < iMaxLength; i++)// iMaxLength ，iMaxLength 。
- {
- foreach (int number in arr)//
- {
- currentItem = number.ToString();//
- try { currnetChar = currentItem[currentItem.Length-i-1]; }//
- catch { listArr[0].Add(number); continue; }// ， listArr[0]。 5 ， ， ， 5 0， listArr[0] 。
- switch (currnetChar)// currnetChar ， 。
- {
- case '0': listArr[0].Add(number); break;
- case '1': listArr[1].Add(number); break;
- case '2': listArr[2].Add(number); break;
- case '3': listArr[3].Add(number); break;
- case '4': listArr[4].Add(number); break;
- case '5': listArr[5].Add(number); break;
- case '6': listArr[6].Add(number); break;
- case '7': listArr[7].Add(number); break;
- case '8': listArr[8].Add(number); break;
- case '9': listArr[9].Add(number); break;
- default: throw new Exception("unknow error");
- }
- }
- for (int j = 0; j < listArr.Length; j++)// ， list
- foreach (int number in listArr[j].ToArray<int>())
- {
- list.Add(number);
- listArr[j].Clear();//
- }
- arr = list.ToArray<int>();//arr
- //Console.Write("{0} times:",i);
- Print(arr);//
- list.Clear();// list
- }
- }
- //
- private static int GetMaxLength(int[] arr)
- {
- int iMaxNumber = Int32.MinValue;
- foreach (int i in arr)//
- {
- if (i > iMaxNumber)
- iMaxNumber = i;
- }
- return iMaxNumber.ToString().Length;// ...
- }
- //
- public static void Print(int[] arr)
- {
- foreach (int i in arr)
- System.Console.Write(i.ToString()+'\t');
- System.Console.WriteLine();
- }
- // 。 0 1000。 iLength
- public static int[] CreateRandomArray(int iLength)
- {
- int[] arr = new int[iLength];
- Random random = new Random();
- for (int i = 0; i < iLength; i++)
- arr[i] = random.Next(0,1001);
- return arr;
- }
- }
- }
- ---------------------------------Code ---------------------------------------------
- ， O (nlog(r)m)， r ， m ， ， 。