内部排序算法的C/C++实现
2017年09月06日
⁄ 综合
⁄ 共 6887字 ⁄ 字号
小 中 大
- 内部排序算法的C/C++实现
- 排序是数据处理中经常使用的一种重要运算,在计算机及其应用系统中,花费在排序上的时间在系统运行时间中占有很大比重;并且排序本身对推动算法分析的发展 也起很大作用。目前已有上百种排序方法,但尚未有一个最理想的尽如人意的方法,本文介绍常用的如下排序方法的C/C++实现,并对它们进行分析和比较。
- 更详细的算法思想的介绍可以参考这里
-
-
- #include <iostream>
- using namespace std;
- void swap(int &a,int &b)
- {
- int tmp;
- tmp=a;
- a=b;
- b=tmp;
- }
- void display(int array[],int len)
- {
- cout<<"the result is:"<<endl;
- for (int i = 0 ;i < len;i++ )
- {
- cout<<array[i]<<" ";
- }
- cout<<endl;
- }
- void bubble_sort(int array[],int len)
- {
-
- for (int i = len-1 ;i >= 0;i-- )
- {
- for(int j = 0;j < i;j++)
- if(array[j] > array[j+1])
- swap(array[j],array[j+1]);
- }
- }
- void insert_sort(int array[],int len)
- {
- int tmp,i,j;
- for(i = 1;i < len;i++)
- {
- if (array[i] < array[i-1])
- {
- tmp = array[i];
- array[i] = array[i-1];
-
- for (j = i-2;j >= 0;j--)
- {
-
- if (array[j] > tmp )
- array[j+1] = array[j];
- else
- {
- array[j+1] = tmp;
- break;
- }
- }
- if(j == -1)
- array[j+1] = tmp;
- }
- }
- }
-
- void bi_insert_sort(int array[],int len)
- {
- int* arr_d = (int *)malloc(sizeof(int) * len);
- arr_d[0] = array[0];
- int head = 0,tail = 0;
- for (int i = 1;i < len; i++ )
- {
- if (array[i] > arr_d[0])
- {
- int j;
- for ( j= tail;j>0;j--)
- {
- if (array[i] < arr_d[j])
- arr_d[j+1] = arr_d[j];
- else
- break;
- }
- arr_d[j+1] = array[i];
- tail += 1;
- }
- else
- {
- if (head ==0)
- {
- arr_d[len-1] = array[i];
- head =len-1;
- }
- else
- {
- int j;
- for (j = head;j <= len-1;j++)
- {
- if (array[i] > arr_d[j])
- arr_d[j-1] = arr_d[j];
- else
- break;
- }
- arr_d[j-1] = array[i];
- head -= 1;
- }
- }
- }
- for (int i = 0;i < len; i++)
- {
- int pos = (i + head );
- if(pos >= len) pos -= len;
- array[i] = arr_d[pos];
- }
- free(arr_d);
- }
-
- void shell_insert(int array[],int d,int len)
- {
- int tmp,j;
- for (int i = d;i < len;i++)
- {
- if(array[i] < array[i-d])
- {
- tmp = array[i];
- j = i - d;
- do
- {
- array[j+d] = array[j];
- j = j - d;
- } while (j >= 0 && tmp < array[j]);
- array[j+d] = tmp;
- }
- }
- }
- void shell_sort(int array[],int len)
- {
- int inc = len;
- do
- {
- inc = inc/2;
- shell_insert(array,inc,len);
- } while (inc > 1);
- }
-
- int partition(int array[],int low,int high)
- {
- int pivotkey = array[low];
- while (low < high)
- {
- while(low < high && array[high] >= pivotkey)
- --high;
- swap(array[low],array[high]);
- while(low < high && array[low] <= pivotkey)
- ++low;
- swap(array[low],array[high]);
- }
- array[low] = pivotkey;
- return low;
- }
- void quick_sort(int array[],int low,int high)
- {
- if (low < high)
- {
- int pivotloc = partition(array,low,high);
- quick_sort(array,low,pivotloc-1);
- quick_sort(array,pivotloc+1,high);
- }
- }
-
- int SelectMinKey(int array[],int iPos,int len)
- {
- int ret = 0;
- for (int i = iPos; i < len; i++)
- {
- if (array[ret] > array[i])
- {
- ret = i;
- }
- }
- return ret;
- }
- void select_sort(int array[],int len)
- {
- for (int i = 0; i < len; i++)
- {
- int j = SelectMinKey(array,i,len);
- if (i != j)
- {
- swap(array[i],array[j]);
- }
- }
- }
-
- void merge(int array[],int i,int m, int n)
- {
- int j,k;
- int iStart = i, iEnd = n;
- int arrayDest[256];
- for ( j = m + 1,k = i; i <= m && j <= n; ++k)
- {
- if (array[i] < array[j])
- arrayDest[k] = array[i++];
- else
- arrayDest[k] = array[j++];
- }
- if (i <= m)
- for (;k <= n; k++,i++)
- arrayDest[k] = array[i];
- if(j <= n)
- for (;k <= n; k++,j++)
- arrayDest[k] = array[j];
- for(j = iStart; j <= iEnd; j++)
- array[j] = arrayDest[j];
- }
- void merge_sort(int array[],int s,int t)
- {
- int m;
- if (s < t)
- {
- m = (s + t )/2;
- merge_sort(array,s,m);
- merge_sort(array,m+1,t);
- merge(array,s,m,t);
- }
- }
-
- void heap_adjust(int array[],int i,int len)
- {
- int rc = array[i];
- for(int j = 2 * i; j <len; j *= 2)
- {
- if(j < len && array[j] < array[j+1]) j++;
- if(rc >= array[j]) break;
- array[i] = array[j]; i = j;
- }
- array[i] = rc;
- }
- void heap_sort(int array[],int len)
- {
- int i;
- for(i = (len-1)/2; i >= 0; i--)
- heap_adjust(array,i,len);
- for( i = (len-1); i > 0; i--)
- {
- swap(array[0],array[i]);
- heap_adjust(array,0,i-1);
- }
- }
- int main() {
- int array[] = {45,56,76,234,1,34,23,2,3,55,88,100};
- int len = sizeof(array)/sizeof(int);
-
-
-
-
-
-
-
-
-
-
- heap_sort(array,len);
- display(array,len);
- return 0;
- }