matlab基数排序,c语言 数据结构 利用随机函数产生n个随机整数，对这些数进行多种方法进行排序... -ag凯发k8国际
满意答案
srand(time(null)); //产生随机数
for(i = 0; i < n; i )
a[i] = rand()%(n - i);
extern void insert(int a[], int x) //插入排序
{
int i;
int n;
int j;
int temp;
n = x;
for(i = 1; i < n; i )
{
temp = a[i];
j = i - 1;
while(temp < a[j] && j >= 0)
{
a[j 1] = a[j];
j--;
}
a[j 1] = temp;
}
}
static void shellsort(int a[], int d, int x)
{
int i;
int j;
int n;
int temp;
n = x;
for(i = d; i < n; i = d)
{
temp = a[i];
j = i - d;
while(a[j] > temp && j >= 0)
{
a[j d] = a[j];
j -= d;
}
a[j d] = temp;
}
}
extern void shell(int a[], int x) //希尔排序
{
int n;
int d;
n = x;
d = n / 2;
while(d > 0)
{
shellsort(a, d, n);
d /= 2;
}
}
extern void bubble(int a[], int x) //冒泡排序
{
int ischange;
int i;
int j;
int n;
n = x;
for(i = n - 1; i > 0; i--)
{
ischange = 0;
for(j = 0; j < i; j )
{
if(a[j 1] < a[j])
{
a[j 1] = a[j];
a[j] = a[j 1] - a[j];
a[j 1] = a[j 1] - a[j];
ischange = 1;
}
}
if(0 == ischange)
{
break;
}
}
}
static int partion(int a[], int left, int right)
{
int l;
int r;
int priv;
l = left;
r = right;
priv = a[l];
while(l < r)
{
while(a[r] > priv && r > l)
r--;
if(l < r)
{
a[l ] = a[r];
}
while(a[l] < priv && r > l)
l ;
if(l < r)
{
a[r--] = a[l];
}
}
a[l] = priv;
return l;
}
static void quicksort(int a[], int left, int right)
{
int l;
int r;
int priv;
l = left;
r = right;
if(l < r)
{
priv = partion(a, l, r);
quicksort(a, l, priv - 1);
quicksort(a, priv 1, r);
}
}
extern void quick(int a[], int n) //快速排序
{
int l;
int r;
l = 0;
r = n - 1;
quicksort(a, l, r);
}
extern void selec(int a[], int x) //选择排序
{
int i;
int j;
int k;
int n;
n = x;
for(i = 0; i < n; i )
{
k = i;
for(j = i; j < n; j )
{
if(a[j] < a[k])
{
k = j;
}
}
if(i != k)
{
a[i] = a[k];
a[k] = a[i] - a[k];
a[i] -= a[k];
}
}
}
static void mergearray(int a[], int first, int mid, int last, int p[])
{
int i;
int j;
int k;
i = first;
j = mid 1;
k = 0;
while(i <= mid && j <= last)
{
if(a[i] <= a[j])
{
p[k ] = a[i ];
}
else
{
p[k ] = a[j ];
}
}
while(i <= mid)
{
p[k ] = a[i ];
}
while(j <= last)
{
p[k ] = a[j ];
}
for(i = 0; i < k; i )
{
a[first i] = p[i];
}
}
static void mergesort(int a[], int first, int last, int p[])
{
int mid;
if(last > first)
{
mid = first (last - first) / 2;
mergesort(a, first, mid, p);
mergesort(a, mid 1, last, p);
mergearray(a, first, mid, last, p);
}
}
extern void merge(int a[], int n) 归并排序
{
int *p;
p = (int *)malloc(n * sizeof(int));
if(!p)
{
perror("malloc");
exit(-1);
}
mergesort(a, 0, n - 1, p);
free(p);
}
static void swap(int data[], int a, int b)
{
data[a] ^= data[b];
data[b] ^= data[a];
data[a] ^= data[b];
}
static void siftup(int data[], int n) // create heap
{
int i;
int p;
for(i = n; i > 1 && data[p = i / 2] > data[i]; i = p)
swap(data, p, i);
}
static void siftdown(int data[], int n) // adjust heap
{
int i;
int c;
i = 1;
while(1)
{
c = 2 * i;
if(c > n)
break;
if(c 1 <= n && data[c 1] < data[c])
c ;
if(data[i] <= data[c])
break;
swap(data, c, i);
i = c;
}
}
static void heapsort(int data[], int n)
{
int i;
for(i = 2; i <= n; i )
{
siftup(data, i);
}
for(i = n; i >= 2; i--)
{
swap(data, 1, i);
siftdown(data, i - 1);
}
}
extern void heap(int a[], int n) //堆排序
{
int *p;
int i;
p = (int *)malloc((n 1) * sizeof(int));
if(!p)
{
perror("malloc");
}
for(i = 0; i < n; i )
*(p i 1) = a[i];
heapsort(p, n);
for(i = 0; i < n; i )
a[i] = *(p i 1);
free(p);
}
基数排序根据你是n进制数，申请n个队列，以空间换取时间，排序复杂度为线性o(n)
12分享举报
总结
以上是ag凯发k8国际为你收集整理的matlab基数排序,c语言 数据结构 利用随机函数产生n个随机整数，对这些数进行多种方法进行排序...的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇：
- 下一篇：