プログラム = データ構造 + アルゴリズム。私たちが作成したものではないプロジェクトを構築するフレームワークの場合、プロジェクトのレベルを実際に判断できるのは、カスタマイズしたデータ構造が便利か、簡潔か、低結合かどうか、これらのメソッドの実装に使用するアルゴリズムが高速かどうかです。効果的で、エラーが発生しにくくなります。あなたがやりたいことが毎日朝から晩までレンガを動かすような仕事ではないのであれば、アルゴリズムを学び、データ構造を分析することがレベルを上げる唯一の方法であることは間違いありません。
アルゴリズムとプログラミング言語は密接な関係がありますが、特定の言語にのみ依存しているわけではありません。実装言語を考慮せずに、通常は次のソート方法があります:
選択ソート
挿入ソート
ヒルソート
マージソート
クイックソート
5 つのソート アルゴリズムを紹介した後、これらのメソッドをまとめて javaAPI に接続します。さらに、これらの並べ替えメソッドの実装を容易にするために、いくつかの補助メソッドを使用します。これらの補助メソッドは非常に単純で、その目的はコードを簡潔にすることです。
/**
* 比较两个大小不同的数字，如果第一个参数比较小则返回true。
*
* @param v 第一个数字
* @param w 第二个数字
* @return 返回比较结果
*/
public static boolean less(int v , int w){ if(v<w) return true; return false;
} /**
* 交换数组中两个索引的内容
*
* @param arr 数组
* @param v 第一个索引
* @param w 第二个索引
*/
public static void exch(int[] arr,int v ,int w){ int temp=arr[v];
arr[v]= arr[w];
arr[w] = temp;
} /**
* 打印数组
*
* @param arr 要显示的数组
*/
public static void show(int[] arr){ for(int i=0;i<arr.length;i++)
System.out.println(arr[i]);
}Java では、ほとんどの要素はオブジェクトであり、これらのオブジェクトの主キーの記述は Comparable メカニズムによって実現され、順序とソートの概念があります。それでは、ソート方法が速いか遅いか、どの程度速いか、そしてどのくらい効率的であるかをどのように研究すればよいでしょうか?各ソートアルゴリズムのコストを以下の観点から検討します。
比較と交換 (並べ替えのコストを判断するには、比較と交換の数を計算する必要があります)
時間 (並べ替えアルゴリズムにかかる時間、またはそれにかかる時間)特定の状況では)
余分なメモリ使用量(一部の並べ替えメソッドは追加のメモリ領域を必要とし、一部の並べ替えメソッドは必要ありません)
一部の特殊な並べ替えアルゴリズムについては特別なコスト見積もりを提供しますメソッド、ほとんどの並べ替えメソッドでは、この方法がどのような状況に適用できるかについては、最後に説明します。結局のところ、これらの無駄な並べ替えは長い間排除されてきました。
選択ソートは、すべてのソートの中で最も単純なソートアルゴリズムです。選択ソートの中心的な考え方は次のとおりです:
配列の先頭で順序付きサブ配列を維持し、順序なし配列の後半で毎回最小の要素を見つけ、それを最初の順序なし要素と交換します。フロントエンドの終了後、この要素をソートします。ソートされた部分配列要素が要素の合計数と等しくなった場合、ソートは完了します。
簡単に言うと、まず配列内の最小の要素を見つけて、それを最初の要素と交換します最初の要素が最小の要素である場合は、それをそれ自体と交換します。次に、2 番目の要素から最後までの最小の要素を見つけて、それを配列の 2 番目の要素と交換するなど、残りの要素の中から最小の要素を選択し続けます。
選択ソートには、固定数の比較N2/2と固定数の交換Nがあります。
比較の数に関して言えば、選択並べ替えでは、最小の要素が何かを知るために、最初の要素から最後の要素までを初めて比較する必要があります。 2 回目では、最小要素を知るために N-1 回の比較が必要になります。合計 N+(N-1)+(N-2)+ ··· + 1 = N2/2 回必要となります。
アルゴリズムのプログラミングにより、最小の要素がすでに正しい位置にある場合でも、その位置をそれ自体と交換する必要があるため、交換の回数もN回に固定されています。
選択ソートの実行時間は固定であり、比較時間の約 N2/2 倍です (N2/2 の場合、基本的に N 回無視できます) 。ソートメソッドの実行時間を推定できない場合でも、ソートメソッドが適切に使用されている限り、その実行時間が N2/2 回を超えることはありません。
package Sort;/**
*
* @author QuinnNorris 选择排序
*/public class Sort1 {
/**
* @param args
*/
public static void main(String[] args) { // TODO Auto-generated method stub
int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }; // 测试数组
sort(arr); // 调用排序算法
Tool.show(arr); // 打印
} /**
* 用选择排序将arr升序排列
*
* @param arr
* 所要排列的数组
*/
public static void sort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++)
if (Tool.less(arr[j], arr[min]))
min = j;
Tool.exch(arr, min, i);
}
}
}选择排序非常简单，他有两个很鲜明的特点：
1.运行时间和输入无关
运行时间和输入无关，好听的讲就是无论多么乱的数据都会在固定的时间之内完成排序，但是更多的情况下，这种前一遍比较不能为后一遍比较提供任何价值的算法是非常费时的。夸张的讲，如果我们要完成某个几乎接近有序的数组的排序，你会发现，使用选择排序所需的时间和去排序那些无序的数组竟然是完全一样的。这在很多情况下是大家不能接受的。
2.数据移动最少
为了保证最少的交换数据，我们不断的进行比较，每次的交换都会百分之百的把一个数字放在正确的位置上。其他的任何排序方法都不具备这个特性。
在选择排序中，一个几乎有序的数组和一个完全无序的数组所需时间是一样的。插入排序则完美的解决了这个问题：
从数组的头部开始，通过不断的一次一位的比较和交换，让每个数据都能插入前端有序部分中自己合理的位置，当所有的元素都完成一遍操作后，排序完成。
我们将要排序的那个元素和前面一位元素比较，如果比前面的元素小，则交换位置，这个元素继续和再前面的元素比较，如果仍然小则继续交换，知道前面的元素小于该元素位置。这个时候，这个不断交换的元素就在这个数组中达到了自己合适的位置，刚才其他被交换的元素，都像是“向后移动一个位置”，为这个元素挪出了空间，这就是插入排序。这种排序很类似我们在打桥牌时整理牌的方法，不断地将牌按照大小从后向前插入。
在一个随机排序而且主键不重复的数组中，平均情况下插入排序需要N2/4次比较以及N2/4次交换。在最坏的情况下需要N2/2次比较和N2/2次交换，最好情况下需要N-1次比较和0次交换。
这个平均情况是怎么计算得出的呢？通常情况下，我们认为数组中的一个数字在整个数组中会被移动半个数组的长度（在平均情况下，每个数字都会移动到有序部分的中间位置，在这种情况下，数字自己的移动和被向后“推”的移动加起来长度为半个数组），在半个数组的移动算作平均情况下，我们得到N2/4的比较和交换次数。
我们可以看出，用插入排序算法排序的时间和这个数组情况有很大关系，如果数组是非常无序的，它的速度要慢于选择排序，但是如果我们现在要排序的数组是几乎完全有序的，那么它的时间将会非常的小。就像我们手中握着一副全都排好顺序的扑克牌，这时你抽到一张梅花9，你可以非常快的将它插到你的手牌中。
数组中每个元素距离他的最终位置不远
一个有序数组的大数组接一个小数组
数组中只有几个元素的位置不正确
上述的三种情况下，使用插入算法会非常非常有效。事实上，当顺序错误的数量很少的时候，插入排序会比其他任何排序算法都快。
package Sort;/**
*
* @author QuinnNorris 插入排序
*/public class Sort2 {
/**
* @param args
*/
public static void main(String[] args) { // TODO Auto-generated method stub
int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }; // 测试数组
sort(arr); // 调用排序算法
Tool.show(arr); // 打印
} /**
* 用插入排序将arr升序排列
*
* @param arr
* 所要排列的数组
*/
public static void sort(int[] arr) {
for (int i = 0; i < arr.length; i++)
for (int j = i; j > 0; j--)
if (Tool.less(arr[j], arr[j - 1]))
Tool.exch(arr, j, j - 1);
}
}在插入排序中，因为他的速度和原有的序列有很大关系。在这里，我们将在原序列中位置顺序颠倒的一对数字叫做倒置，这只是我们起的一个名字，它表示两个数字的位置是错误的（a应该在b的前面，但是在数组中a在b的后面，无论a与b相隔多远，都可以称a、b是一个倒置）。插入排序具有以下几点特性：
交换和比较的次数相同
比较的次数大于等于倒置的数量
比较的次数小于等于倒置数量加上数组的大小再减一
除此之外，插入排序作为一种初级排序算法，会在之后的高级排序算法中作为一个中间算法频频出现，我们会在以后再见到他。
这两种算法是如此的相似，以至于我们非常好奇想将他们比较一番。对于随机排序无重复的数组，插入排序和选择排序的运行时间都是平方级别的，所以两者只比应该是一个较小的常数。
次に紹介するソートアルゴリズムは主要なソートアルゴリズムではありませんが、実際には挿入アルゴリズム技術を使用して実装されています。ヒルソートとは次のことを指します:
大きい値から小さい値まで定数 h 値を定式化し、ソートを挿入することにより、配列内の h の任意の間隔を持つ要素が順序付けされます。 h=1 になるまで h のサイズを減らし続け、配列全体が順序付けされます。
最初は順番のないトランプを持っていますが、突然この方法は遅すぎると感じます。最初に大まかなスクリーニングを行います。いくつかのカードは順番に配置されますが、他のカードは順番に配置されません。このようにして、カードを何度かふるいにかけて、最終的に手札のすべてのカードを順番に並べます。これがヒルソートです。
何千もの配列をソートする必要がある場合、通常はヒルソートを使用できます。
ヒルソートでは、最初に h を定義し、h を間隔として部分配列を分割し、挿入アルゴリズムを使用してこの部分配列をソートします。次に、h を小さくし続け、新しい配列を並べ替えます。最後に、h が 1 の場合、この並べ替えによってすべてのデータが順序付けされます。
では、ヒルソートの利点は何でしょうか?挿入ソートの利点は、部分的に順序付けされたシーケンスのソートが非常に高速であり、小さな配列のソートも非常に高速であることです。当社のヒルソーティングは、これら 2 つの利点を兼ね備えています。 h が大きい場合、配列全体は比較的小さくなり、h が小さい場合、配列全体が徐々に整然となります。このとき、挿入ソートを使用することも非常に良い選択です。ヒルソートはこれら 2 つの利点を兼ね備えており、全体の時間が比較的速いと言えます。
ヒルソートについては、以下の理由により、上記の分析方法に従って分析するつもりはありません。まず第一に、Hill ソートは交換と比較を研究するのが非常に困難です。重要な要素は h であり、h は定数であり、異なる h を設定することでこのジャンプの間隔を変更できるからです。そして明確な説明はありません: 最良の効果を達成するために h はどのような規則に従うのでしょうか (通常は 3*h+1 を使用できます。つまり、1、4、13、40、121、364... この数字のグループは次のとおりです) h)として使用されます。 h は決定できないため、最適な時間はありません。
中規模の配列の場合、ヒル ソートの実行時間は許容範囲内であるため、経験豊富なプログラマはヒル ソートを使用することがあります。コードの量は非常に少なく、追加のメモリ領域は使用されません。おそらく、より高速なアルゴリズムがあるかもしれませんが、N が大きい場合、それらはおそらくヒル ソートの 2 倍未満しか高速ではありません。そしてそれはとても複雑です。並べ替える必要があるが体系的な並べ替え機能がない場合は、ヒル ソートの使用を検討し、その後、より高度な並べ替え方法に置き換えるかどうかを検討してください。
プログラム = データ構造 + アルゴリズム。私たちが作成したものではないプロジェクトを構築するフレームワークの場合、プロジェクトのレベルを実際に判断できるのは、カスタマイズしたデータ構造が便利か、簡潔か、低結合かどうか、これらのメソッドの実装に使用するアルゴリズムが高速かどうかです。効果的で、エラーが発生しにくくなります。あなたがやりたいことが毎日朝から晩までレンガを動かすような仕事ではないのであれば、アルゴリズムを学び、データ構造を分析することがレベルを上げる唯一の方法であることは間違いありません。
上記は Java アルゴリズム (1) - 一次ソート アルゴリズムの内容です。さらに関連する内容については、PHP 中国語 Web サイト (m.sbmmt.com) に注目してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
