插入排序是假设一一个数组中的前一段(或者后一段)已经排好序,而将剩下的元素分别插入到合适的位置上,以达到排序目的的一种算法
以下是实现代码,对红色部分有不同的实现方法:- /// <summary>
- /// 插入排序
- /// </summary>
- /// <param name="arr">要排序的数组</param>
- static void InsertSort1( ref int[] arr)
- {
- int keyValue = 0;
- int pos = 0;
- for (int key = 1; key < arr.Length;key++ )
- {
- keyValue = arr[key];
- pos = key - 1;
- while (pos >= 0 && arr[pos] > keyValue)
- {
- arr[pos + 1] = arr[pos];
- pos--;
- }
- arr[pos + 1] = keyValue;
- }
- }
- /// <summary>
- /// 插入排序
- /// </summary>
- /// <param name="arr">要排序的数组</param>
- static void InsertSort2(ref int[] arr)
- {
- int key;
- for (int i = 1; i < arr.Length;i++ )
- {
- key = i - 1;
- while(key >=0 && arr[key] > arr[key+1])
- {
- Swap(ref arr[key], ref arr[key + 1]);
- key --;
- }
- }
- }
- /// <summary>
- /// 交换两个数的值
- /// </summary>
- /// <param name="i">左值</param>
- /// <param name="j">右值</param>
- static void Swap(ref int i,ref int j)
- {
- int temp = i;
- i = j;
- j = temp;
- }
复制代码 插入排序采用的是减治法,关于减治法的概念可以百度一下(哈哈,偷懒了)
关于其他算法请参考这里
|