ソートアルゴリズム学習ノート-C言語バージョン
8504 ワード
//泡立ち順
//概要:バブルソートは、ソートされた記録配列R[1..n]を垂直に並べ、各記録R[i]は、重量kiの気泡と見なされる.
//軽気泡は重気泡の下ではいけないという原則に基づき、配列Rを下から上へ走査する.本原則に違反する軽い気泡をスキャンすると、それを上に「浮遊」させる.
//最後の2つの気泡がいずれも軽いものが上、重いものが下になるまで繰り返します.
//直接選択ソート
//profile:ソートを直接選択するプロセスは、まずすべてのレコードの中でシーケンスコードの最小のレコードを選択し、それを1番目のレコードと交換します.
//そして残りのレコードの中からソートコードの最小のレコードを選び、2番目のレコードと交換する…すべてのレコードが並ぶまで順番に類推します.
//並べ替えを直接挿入
//概要挿入ソートのプロセスは、i番目のレコードを挿入する場合、R 1,R 2,..Ri-1はすでに順番に並んでいて、
//i番目のレコードのソートコードKiをR 1,R 2,.,Ri−1のソートコードを1つずつ比較し,適切な位置を見つけた.
//直接挿入ソートを使用して、n個のレコードを持つファイルに対して、n-1本のソートを行います.
//クイックソート
//概要:クイックソートはC.A.R.Hoareが1962年に提出した.基本的な考え方は
//1回のソートでソートするデータを独立した2つの部分に分割し、その一部のすべてのデータは他の部分のすべてのデータよりも小さく、
//そして、この方法でこの2つのデータをそれぞれ迅速にソートし、ソートプロセス全体を再帰的に行い、データ全体が秩序化されたシーケンスになるようにします.
//並べ替え:
//概要:集計ソートは集計操作に確立された有効なソートアルゴリズムです.
//このアルゴリズムは、分割法(Divide and Conquer)を用いた非常に典型的な応用である.
//既存のシーケンスのサブシーケンスを結合し、完全に秩序化されたシーケンスを得る.すなわち、各サブシーケンスを秩序化してから、サブシーケンスセグメント間を秩序化する.
//2つの順序テーブルを1つの順序テーブルにマージする場合は、2ウェイ集計と呼ばれます.
//基数ソート
//概要:基数ソート(radix sort)は「分配ソート(distribution sort)」に属し、
//「バケツ法」(bucket sort)やbin sortとも呼ばれ、その名の通りキー値の一部の情報を通じて、
//ソートする要素をいくつかの「バケツ」に割り当て、ソートの役割を果たすために、基数ソート法は安定性のあるソートに属します.
//その時間複雑度はO(nlog(r)m)であり、rは採用された基数であり、mはスタック数であり、場合によっては、
//基数ソート法の効率は他の安定性ソート法より高い.
//概要:バブルソートは、ソートされた記録配列R[1..n]を垂直に並べ、各記録R[i]は、重量kiの気泡と見なされる.
//軽気泡は重気泡の下ではいけないという原則に基づき、配列Rを下から上へ走査する.本原則に違反する軽い気泡をスキャンすると、それを上に「浮遊」させる.
//最後の2つの気泡がいずれも軽いものが上、重いものが下になるまで繰り返します.
#include
#define n 10
int main()
{
int i, j,temp;
int array[10] = { 1, 2, 0, 5, 9,3, 4, 6, 7, 8 };
for (i = 0; i < n- 1;i++) //
for (j = 0; j < n- 1 - i;j++) // i
{
if (array[j+1] //直接選択ソート
//profile:ソートを直接選択するプロセスは、まずすべてのレコードの中でシーケンスコードの最小のレコードを選択し、それを1番目のレコードと交換します.
//そして残りのレコードの中からソートコードの最小のレコードを選び、2番目のレコードと交換する…すべてのレコードが並ぶまで順番に類推します.
#include
#define n 10
int main()
{
int i, j, k,temp;
int a[n] = { 9, 5, 1, 6, 2, 3, 8,4, 7, 0 };
for (i = 0; i < n - 1; i++)
{
k = i;
for (j = i + 1; j< n; j++)
{
if(a[k]>a[j])
k= j;
}
if (k != i)
{
temp =a[i];
a[i] =a[k];
a[k] =temp;
}
}
for (i = 0; i <= 9; i++)
{
printf("%3d",a[i]);
}
return 0;
} //並べ替えを直接挿入
//概要挿入ソートのプロセスは、i番目のレコードを挿入する場合、R 1,R 2,..Ri-1はすでに順番に並んでいて、
//i番目のレコードのソートコードKiをR 1,R 2,.,Ri−1のソートコードを1つずつ比較し,適切な位置を見つけた.
//直接挿入ソートを使用して、n個のレコードを持つファイルに対して、n-1本のソートを行います.
#include
#define N 10
int main()
{
int i,j ,temp,a[N] = { 0, 5, 9, 3,2, 7, 6, 4, 1, 8 };
for (int i = 1; ia[i])
{
temp =a[i];
for (j= i - 1; j >= 0 && a[j]>temp; j--)
{// ，
a[j+ 1] = a[j];
}
a[j +1] = temp;// a[j+1]=temp;
}
}
for (i= 0; i < 10; i++)
{
printf("%3d",a[i]);
}
return 0;
} //クイックソート
//概要:クイックソートはC.A.R.Hoareが1962年に提出した.基本的な考え方は
//1回のソートでソートするデータを独立した2つの部分に分割し、その一部のすべてのデータは他の部分のすべてのデータよりも小さく、
//そして、この方法でこの2つのデータをそれぞれ迅速にソートし、ソートプロセス全体を再帰的に行い、データ全体が秩序化されたシーケンスになるようにします.
#include
void sort(int a[],int left, int right)
{
int i, j, t, temp;
if (left > right)
return ;
temp = a[left];
i = left;
j = right;
if (i!= j)
{
while (a[j] >temp && j > i)
j--;
while (a[i] //並べ替え:
//概要:集計ソートは集計操作に確立された有効なソートアルゴリズムです.
//このアルゴリズムは、分割法(Divide and Conquer)を用いた非常に典型的な応用である.
//既存のシーケンスのサブシーケンスを結合し、完全に秩序化されたシーケンスを得る.すなわち、各サブシーケンスを秩序化してから、サブシーケンスセグメント間を秩序化する.
//2つの順序テーブルを1つの順序テーブルにマージする場合は、2ウェイ集計と呼ばれます.
#include
void mergesort(intarray[], int temparray[], int start_index, int end_index)
{
int middle=(start_index+end_index)/2;
int i = start_index, j = middle, k= start_index;
if (start_index < end_index)
{
mergesort(array,temparray,start_index,middle);
mergesort(array,temparray,middle+1,end_index);
while (i != middle&& j != end_index)
{
if(array[i] < array[j])
temparray[k++]= array[i++];
else
temparray[k++]= array[j++];
}
while (i != middle)
{
temparray[k++]= array[i++];
}
while (j !=end_index)
{
temparray[k++]= array[j++];
}
for (i =start_index; i < end_index; i++)
{
array[i]= temparray[i];
}
}
}
int main()
{
int a[8] = { 50, 10, 20, 30, 70,40, 80, 60 };
int i, b[8];
mergesort(a, b, 0, 7);
for (i = 0; i<8; i++)
printf("%d ", a[i]);
printf("
");
return 0;
} //基数ソート
//概要:基数ソート(radix sort)は「分配ソート(distribution sort)」に属し、
//「バケツ法」(bucket sort)やbin sortとも呼ばれ、その名の通りキー値の一部の情報を通じて、
//ソートする要素をいくつかの「バケツ」に割り当て、ソートの役割を果たすために、基数ソート法は安定性のあるソートに属します.
//その時間複雑度はO(nlog(r)m)であり、rは採用された基数であり、mはスタック数であり、場合によっては、
//基数ソート法の効率は他の安定性ソート法より高い.
#include
#include
//
int getmax(int *a,int n)
{
int max = a[0];
for (int i = 1; i < n; i++)
{
if (a[i]>max)
max =a[i];
}
return max;
}
//
int getlooptime(intmax)
{
int count = 1;
while (max / 10 != 0)
{
max = max / 10;
count++;
}
return count;
}
// 2
void sort2(int *a,int n,int times)
{
int b[10][10] = {};//
// index
// 798 index=(798/1)%10=8
// index=(798/10)%10=9
// index=(798/100)%10=7
//tempNum 1、10、100
int tempnum = pow((float)10,times-1);
int i, j;
//
for (int i = 0; i < n;i++)
{
int row_index = (*(a+ i) / tempnum)%10;
for (j = 0; j <10; j++)
{
if(b[row_index][j] == NULL)
{
b[row_index][j]= *(a + i);
break;
}
}
}
//
int k = 0;
for (i = 0; i < 10;i++)
for (j = 0; j < 10; j++)
{
if (b[i][j] != NULL)
{
*(a +k) = b[i][j];
b[i][j]= NULL;
k++;
}
}
}
// 1
void sort(int *a,int n)
{
int max, sorttimes;
max = getmax(a, n);
sorttimes = getlooptime(max);
printf("%d %d
", max,sorttimes);
for (int i = 1; i <= sorttimes;i++)
{
sort2(a, n, i);
}
}
int main()
{
int a[6] = { 5, 10, 123, 21, 11,1234 };
int n = sizeof(a) / sizeof(int);//
sort(a,6);
for (int i = 0; i < 6; i++)
{
printf("%d",a[i]);
}
return 0;
}