1、递归实现插入排序
基本思想:
可以把插入排序看作递归 地排序A[1..n-1]然后插入a[n]到已经排好序的序列a[1..n-1]中。
一下是实现算法(C#描述,VS205中调试通过)
class
InsertSort
...
{
static void Main(string[] args)
...{ int[] array1=...{15,1,2333,4,5,67,24,645,253,8,9,34,22,100,22,23,45,67};
ISort(array1, array1.Length);
for (int i = 0; i < array1.Length; i++)
...{
Console.WriteLine(array1[i]);
}
Console.Read();
}
//递归实现插入排序
static void ISort(int[] a,int n)
...{
if (n > 2)
ISort(a, n - 1);
InsertToArray(a[n - 1], a, n - 2);
}
private static void InsertToArray(int data, int[] a, int last)
...{
while (last>=0 && data < a[last])
...{
a[last + 1] = a[last];
last--;
}
a[last + 1] = data;
}
}
2、描述一个时间复杂度为o(nlgn)的算法找到在集合S中和为x的两个元素
基本思想:对集合s进行排序,时间复杂度为o(nlgn)的排序算法有快速排序,堆排序和归并排序。然后对已经排好序的序列进行一遍扫描找到两个元素。使得整个算法的时间复杂度为O(nlogn)。
实现算法(C#描述,VS205中调试通过,采用快速排序)
class
ElementsInS
...
{
static void Main(string[] args)
...{
Console.WriteLine("请输入数组S中的元素,以","分开");//输入数组S
string s =Console.ReadLine(); //生成数组S
string[] a = s.Split(',');
List<int> ls = new List<int>() ;
foreach(string t in a)
...{
int i;
if(int.TryParse(t,out i))
ls.Add(i);
}
Console.WriteLine("请输入数字S:");
int x =int.Parse(Console.ReadLine()); //输入和x
int[] aa = new int[ls.Count]; //从List copy数组s
ls.CopyTo(aa,0);
myQuickSort(aa, 0, ls.Count-1); //先对其进行快速排序时间复杂度为O(nlgn)
//以下循环一遍寻找两个元素
int f = 0;
int l = aa.Length-1;
while(f<l)
...{
if(aa[f]+aa[l] == x)
...{
Console.WriteLine("已经找到S的俩元素:" + aa[f].ToString() + "和" + aa[l].ToString());
break; //找到元素
}
else if(aa[f]+aa[l]>x) //两数和大数已知数时,移动尾游标
--l;
else //两数和小于已知数时, 移动头游标
++f;
}
if (f >= l)
...{
Console.WriteLine("数组s中没有和为" + x.ToString() + "的俩元素");
}
Console.ReadLine();
}
//以下为快速排序
private static void Swap(ref int i, ref int j)
//swap two integer
...{
int t;
t = i;
i = j;
j = t;
}
public static void Sort(int[] list, int low, int high)
...{
if (high <= low)
...{
//only one element in array list
//so it do not need sort
return;
}
else if (high == low + 1)
...{
//means two elements in array list
//so we just compare them
if (list[low] > list[high])
...{
//exchange them
Swap(ref list[low], ref list[high]);
return;
}
}
//more than 3 elements in the arrary list
//begin QuickSort
myQuickSort(list, low, high);
}
public static void myQuickSort(int[] list, int low, int high)
...{
if (low < high)
...{
int pivot = Partition(list, low, high);
myQuickSort(list, low, pivot - 1);
myQuickSort(list, pivot + 1, high);
}
}
private static int Partition(int[] list, int low, int high)
...{
//get the pivot of the arrary list
int pivot;
pivot = list[low];
while (low < high)
...{
while (low < high && list[high] >= pivot)
...{
high--;
}
if (low != high)
...{
Swap(ref list[low], ref list[high]);
low++;
}
while (low < high && list[low] <= pivot)
...{
low++;
}
if (low != high)
...{
Swap(ref list[low], ref list[high]);
high--;
}
}
return low;
}
}