冒泡排序
namespace BubbleSorter
{
public class MainClass
{
public static void Main()
{
//int[] iArrary = new int[] { 1, 2, 3, 6, 7 }; //最好的情况,外循环1次,内循环4次 ,为n-1,时间复杂度为n-1=O(n)
int[] iArrary = new int[] { 7, 6, 3, 2, 1 }; //最坏的情况,外循环4次,内循环分别4,3,2,1次 为n(n-1)/2,每次循环带来3次数据交换,所以时间复杂度为3*n*(n-1)/2=O(n2)
//影响冒泡算法效率主要是交换数据带来的移动效率低
BubbleSort(iArrary);
Console.Read();
}
//冒泡排序(Bubble Sort)的基本思想是:将相邻的记录的关键码进行比较,若前面记录的关键码大于后面记录的关键码,则将它们交换,否则不交换。
public static void BubbleSort(int[] list)
{
int temp;
bool IfChanged = false;//默认没有交换数据
for (int j = 1; j <= list.Length -1; j++)
{
for (int i = 0; i <= list.Length - j -1; i++)
{
if (list[i] > list[i + 1])
{
IfChanged = true; //交换了数据
temp = list[i];
list[i] = list[i + 1];
list[i + 1] = temp;
}
}
if (IfChanged == false) break; //如果没有发生数据交换,直接退出
IfChanged = false; //恢复默认值
Console.WriteLine("第" + j.ToString() + "次排序的结果");
for (int m = 0; m < list.Length; m++)
{
Console.Write("{0} ", list[m]);
}
Console.WriteLine();
}
}
}
}
选择排序
using System;
namespace SelectionSorter
{
public class SelectionSorter
{
private int min;
public void Sort(int[] list)
{
for (int i = 0; i < list.Length - 1; i++)
{
min = i;
for (int j = i + 1; j < list.Length; j++)
{
if (list[j] < list[min])
min = j;
}
int t = list[min];
list[min] = list[i];
list[i] = t;
}
}
}
public class MainClass
{
public static void Main()
{
int[] iArrary = new int[] { 1,3,2,7,6 };
SelectionSorter ss = new SelectionSorter();
ss.Sort(iArrary);
for (int m = 0; m < iArrary.Length; m++)
Console.Write("{0} ", iArrary[m]);
Console.WriteLine();
Console.Read();
}
}
}
插入排序
using System;
namespace InsertionSorter
{
public class InsertionSorter
{
public void Sort(int[] list)
{
for (int i = 1; i < list.Length; i++)
{
int t = list[i];
int j = i;
while ((j > 0) && (list[j - 1] > t))
{
list[j] = list[j - 1];
--j;
}
list[j] = t;
}
}
}
public class MainClass
{
public static void Main()
{
int[] iArrary = new int[] { 1,3,2,7,6 };
InsertionSorter ii = new InsertionSorter();
ii.Sort(iArrary);
for (int m = 0; m < iArrary.Length; m++)
Console.Write("{0}", iArrary[m]);
Console.WriteLine();
Console.Read();
}
}
}
希尔排序
using System;
namespace ShellSorter
{
public class ShellSorter
{
public void Sort(int[] list)
{
int inc;
for (inc = 1; inc <= list.Length / 9; inc = 3 * inc + 1) ;
for (; inc > 0; inc /= 3)
{
for (int i = inc + 1; i <= list.Length; i += inc)
{
int t = list[i - 1];
int j = i;
while ((j > inc) && (list[j - inc - 1] > t))
{
list[j - 1] = list[j - inc - 1];
j -= inc;
}
list[j - 1] = t;
}
}
}
}
public class MainClass
{
public static void Main()
{
int[] iArrary = new int[] { 1,3,2,7,6 };
ShellSorter sh = new ShellSorter();
sh.Sort(iArrary);
for (int m = 0; m < iArrary.Length; m++)
Console.Write("{0} ", iArrary[m]);
Console.WriteLine();
Console.Read();
}
}
}
|