设有一元素为整数的线性表L=(a1,a2,a3,?,an),存放在一维数组A[N]中,设计一个算法

Question

设有一元素为整数的线性表L=(a1,a2,a3,?,an),存放在一维数组A[N]中,设计一个算法,以表中an作为参考元素,将该表分为左、右两部分,其中左半部分每个元素小于等于an,右半部分每个元素都大于an, an位于分界位置上(要求结果仍存放在A[N]中)。

Answer 1

上面是核心代码和一个随手写的简单测试，注意看数字15，左边都比15小，右边都比15大。

你的这个题目其实就是快速排序算法的一部分，有兴趣可以去看看快排的原理，我这个函数就是从之前写的快排拿出来小改了一下的。

下面是完整的测试函数，随手写的，可能不太优雅：

#include <bits/stdc++.h>

using namespace std;

void halfSort(int* v, int low, int high, int k) {

  int mid = k, i = low, j = high;

  while (true) {

    while (v[j] > v[mid] && j != i) {

      --j;

    }

    while (v[i] <= v[mid] && j != i) {

      ++i;

    }

    if (j != i) {

      v[j] += v[i];

      v[i] = v[j] - v[i];

      v[j] -= v[i];

    } else {

      int temp = v[j];

      v[j] = v[mid];

      v[mid] = temp;

      mid = j;

      break;

    }

  }

}

int main(void) {

  int arr[45];

  for (int i = 0; i < 45; ++i) {

    arr[i] = 45 - i;

  }

  int k = 30;

  printf("k = %d, arr[k] = %d\n", k, arr[k]);

  halfSort(arr, 0, 44, k);

  for (int i = 0; i < 45; ++i) {

    printf("%d ", arr[i]);

  }

  return 0;

}

Answer 2

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 20

int main()
{
int s[N];
srand((unsigned)time(0));
int i,j;
for(i=0;i<N;i++)
{
s[i]=rand()%200;
}
printf("\n源表\n");
for(i=0;i<N;i++)
{
printf("%d ",s[i]);
}

int left_i=0, right_i=N-2;
while(1)
{
if(s[left_i]>s[N-1])
{
while(1)
{
if(s[right_i]<s[N-1])
{
printf("\n-->\n");
for(i=0;i<N;i++)
{
printf("%d",s[i]);
if(i==left_i || i==right_i)
{
printf("^");
}
else
{
printf(" ");
}
}
j=s[left_i];
s[left_i]=s[right_i];
s[right_i]=j;
right_i--;
break;
}
else
{
right_i--;
if(right_i<=left_i)
{
break;
}
}
}
}
left_i++;
if(right_i<=left_i)
{
break;
}
}
printf("\n现表\n");
for(i=0;i<N;i++)
{
printf("%d ",s[i]);
}
return 0;
}

本回答被网友采纳