前段时间找实习的时候，为了学习算法和数据结构，自己总结和其他渠道得来了一些基本的排序和查找算法，使用C++的模板实现，在此不进行复杂度分析只作为日后使用作参考，直接上代码。
一、排序
1.直接插入
template<typename Type> void InsertionSort(Type Array[],int length)
{ int index,j; Type temp; for(index = 1;index < length;index++) { j = index; temp = Array[index]; while(j> 0 && temp<Array[j- 1]; { Array[j] = Array[j- 1]; j--; } Array[j] = temp; } }
2.简单选择排序
template <typename Type> void SelectionSort(Type Array[],int length)
{ int index,j; int smallIndex; Type temp; for(index = 0;index<length- 1;index++) { smallIndex = index; for(j=smallIndex+ 1;j<length;j++) { if(Array[j]<Array[smallIndex]) smallIndex = j; } temp = Array[index]; Array[index] = A[smallIndex]; A[smallIndex] = temp; } }
3.冒泡排序
template<typename Type> void BubbleSort(Type Array[],int length)
{ int index,j; int lastExchangeIndex; Type temp; for(index = length- 1;index> 0;) { lastExchangeIndex = 0; for( j = 0;j<index;j++) { if(Array[j+ 1]<Array[j]) { temp = Array[j]; Array[j]= Array[j+ 1]; Array[j+ 1]=temp; lastExchangeIndex = j; } } index = lastExchangeIndex; } }
4.希尔（Shell）排序
template<typename Type> void ShellInsert(Type Array[],int dk,int length)
{ Type temp; int index = 0,j = 0; for(index=dk;index<length;index++) { if(Array[index]<Array[index-dk] { temp = Array[index]; for(j=index-dk;j>= 0&&temp<Array[j];j-=dk) { Array[j+dk] = Array[j]; } Array[j+dk] = temp; } } } template<typename Type> void ShellSort(Type Array[], int dlta[], int length1, int length2) { int k; for(k = 0;k<length2;k++) { ShellInsert(Array,dlta[k],length1); } }
5.堆排序
template<typename Type> void HeapAdjust(Type Array[], int start , int size) { int j; Type temp = Array[start]; for(j= 2*start;j<=size;j*= 2) { if(j<size && Array[j]<Array[j+ 1]) ++j; if(!(temp<Array[j]) break; Array[start] = Array[j]; start = j; } Array[start] = temp; } template<typename Type> void HeapSort(Type Array[], int n) { int i,j; Type temp; for( i = n/ 2;i> 0;i--) HeapAdjust(Array,i,n); for(j=n;j> 1;j--) { temp = Array[j]; Array[j]= Array[i]; Array[i]=temp; HeapAdjust(Array, 1,j- 1); }
}
6.快速排序
template<typename Type> int Partition(Type Array[],int low,int high)
{ Type temp = Array[low]; while(low < high) { while(low<high && temp<=Array[high]) --high; Array[low] = Array[high]; while(low<high && temp>=Array[low]) ++low; Array[high] = Array[low]; } Array[low] = temp; return low; } template<typename Type> void QuickSort(Type Array[], int low, int high) { int pivotloc = 0; if(low <high) { pivotloc = Partition(Array,low,high); QuickSort(Array,low,pivotloc- 1); QuickSort(Array,pivotloc+ 1,high); } }
7.归并排序（链表和数组）
void Merge(LinkList La,LinkList Lb,LinkList Lc)
{ LinkList pa = La->next,pb = Lb->next,pc = Lc->next; while(pa && pb) { if(pa->data <= pb->data) { pc->next = pa; pc = pa; pa = pa->next; } else{ pc->next = pb; pc = pb; pb = pb->next; } } pc->next = pa?pa:pb; free(Lb); } / void TwoMerge( int ArrayA[], int ArrayB[], int s, int m, int e) { int i = s, j = m+ 1 , k = s; while(i<=m && j<=e) { if(ArrayA[i] <= ArrayA[j]) { ArrayB[k] = ArrayA[i]; i++; k++; } else{ ArrayB[k] = ArrayA[j]; j++; k++; } } while(i<=m) { ArrayB[k] = ArrayA[i]; i++; k++; } while(j<=e) { ArrayB[k] = Array[j]; j++; k++; } } void TwoMergeSort( int ArrayA[], int left, int right) { int Temp[NUM]; if(left >=right) { return; } else if(left + 1 == right) {
if(ArrayA[left]>ArrayA[right])
{ int temp = ArrayA[left]; ArrayA[left]=ArrayA[right]; ArrayA[right] = temp; } }else{ int mid = (left + right)/2; TwoMergeSort(Array,left,mid); TwoMergeSort(Array,mid+1,right); TwoMergeSort(Array,Temp,left,mid, right); }}8.折半插入排序
template<typename Type> void BinInsertionSort(Type Array[],int length+1)
{ int index,j; Type temp; int low,hign,mid; for(index = 2;index<=length;i++) { Array[ 0] = Array[index]; low = 1; high = index - 1; while(low <= high) { mid = (low+high)/ 2; if(Array[ 0] <Array[mid]) high = mid - 1; else low = mid + 1; } for(j = index - 1;j>=high+ 1;j--) Array[j+ 1]= Array[j]; Array[high+ 1]=Array[ 0]; } }
9.奇偶排序
template<typename Type> void OESort(Type Array[],int length)
{ int change = 1; int OddIndex,EvenIndex; Type temp; while(change) { change = 0; for(OddIndex = 1;OddIndex<length- 1;OddIndex += 2) { if(Array[OddIndex]>Array[OddIndex+ 1]) { temp = Array[OddIndex]; Array[OddIndex] = Array[OddIndex+ 1]; Array[OddIndex+ 1] = temp; change = 1; } } for(EvenIndex = 0;EvenIndex <length- 1;EvenIndex += 2) { if(Array[EvenIndex] > Array[EvenIndex+ 1]) { temp = Array[EvenIndex]; Array[EvenIndex] = Array[EvenIndex+ 1]; Array[EvenIndex + 1] = temp; change = 1; } } } }
10.两端冒泡排序
template<typename Type> void DubBubble(Type Array[], int length) { int index = 0,j; int sorted = 0; Type temp; while(!sorted) { sorted = 1; for(j=length-index- 1;j>index;j--) { if(Array[j] <Array[j- 1]) { sorted = 0; temp=Array[j];Array[j]=Array[j- 1];Array[j- 1]=temp; } } for(j = index;j<length-index- 2;j++) { if(Array[j]>Array[j+ 1] { sorted = 0; temp=Array[j];Array[j]=Array[j+ 1];Array[j+ 1]=temp; } } index++; }
}
二、查找
1.顺序查找
template<typename Type> int SeqSearch(Type list[],int length,Type key)
{ for( int index = 0;index <length;index++) { if(list[index] ==key) return index; } return - 1;
}
2.折半查找
template<typename Type> int BinSearch(Type list[],int length,Type key)
{ int mid,low,high; low = 0; high = length- 1; while(low<high) { mid = (low + high)/ 2; if(key == list[mid]; return mid; else if(key<list[mid]); high = mid - 1; else low = mid + 1; } return - 1; }